Aller au contenu
Omnikalc

Calculateur du problème des pièces de Frobenius

Saisissez deux valeurs de pièces ou de lots pour obtenir le plus grand montant impossible à former, le nombre de montants impossibles, le montant à partir duquel tout total est possible et si les deux valeurs sont premières entre elles.

Mis à jour le
Vos paramètres

Valeur hors limites

Valeur hors limites

Résultats

Plus grand montant impossible (nombre de Frobenius)

31

Nombre de montants impossibles

16

Tout montant à partir de cette valeur peut être formé (conducteur)

32

Plus grand commun diviseur des deux valeurs
1
Premiers entre eux (1 = oui, 0 = non)
1
Plus petit commun multiple
45

Le calculateur du problème des pièces de Frobenius donne le plus grand montant impossible à former avec deux valeurs de pièces ou de lots, le nombre de montants impossibles, le conducteur à partir duquel tout est possible et si les deux valeurs sont premières entre elles.

Comment se fait le calcul

  • Saisissez les deux valeurs, comme des valeurs de pièces, de timbres ou des tailles de lots.
  • Le calculateur trouve leur plus grand commun diviseur pour vérifier qu’elles sont premières entre elles.
  • Lisez le nombre de Frobenius, le nombre de montants impossibles et le conducteur.

Exemple

Avec des valeurs de 9 et 5, le plus grand commun diviseur est 1 (indicateur de primalité entre elles 1), donc le plus grand montant impossible à former est 31. Il y a 16 montants impossibles, et tout montant à partir de 32 est possible. Le plus petit commun multiple est 45.

Pourquoi c’est utile

Le calculateur aide les étudiants, enseignants, amateurs de casse-têtes, caissiers et planificateurs qui veulent savoir quels totaux peuvent être payés avec deux valeurs de pièces ou de timbres, ou quelles quantités peuvent être commandées avec deux tailles de lots, et pourquoi les grands totaux marchent toujours.

À savoir

Utilisez des nombres entiers de 2 à 600. Si les valeurs ne sont pas premières entre elles, divisez-les d’abord par leur plus grand commun diviseur et traitez le problème dans les nouvelles unités, car seuls les multiples du diviseur peuvent être formés. La formule vaut pour exactement deux valeurs, donc pour trois ou plus il faut une recherche informatique. Le nombre de montants impossibles ne compte pas zéro, toujours possible sans pièce. Pour une vérification rapide à la main, listez les multiples de la plus petite valeur et ajoutez la plus grande à plusieurs reprises : la première série de montants possibles consécutifs aussi longue que la plus petite valeur marque le point à partir duquel tout marche.

Outils liés

Le calculateur du PGCD et du PPCM trouve diviseurs et multiples, celui de la tirelire compte les pièces, celui du théorème des nombres premiers estime les nombres premiers et celui des nombres polygonaux explore des motifs numériques.

Questions fréquentes

Qu’est-ce que le problème des pièces de Frobenius ?

Il demande le plus grand montant qui ne peut pas être payé exactement avec des pièces de valeurs données, utilisées autant de fois que nécessaire. Avec seulement deux valeurs premières entre elles a et b, la réponse est le nombre de Frobenius a × b − a − b, connu depuis Sylvester en 1882. Au-dessus de ce montant, tout total peut être formé.

Pourquoi les valeurs doivent-elles être premières entre elles ?

Si les deux valeurs ont un diviseur commun, tout montant formé est un multiple de celui-ci, donc une infinité de montants sont impossibles et il n’y a pas de plus grand. Le calculateur affiche alors zéro pour le nombre de Frobenius et les autres résultats. Il indique le plus grand commun diviseur pour vérifier.

Combien de montants sont impossibles ?

Sylvester a montré que exactement (a − 1)(b − 1) / 2 montants positifs ne peuvent pas être formés. Pour 5 et 9, il y en a 16, et le plus grand est 31. Exactement la moitié des montants de 0 au conducteur (a − 1)(b − 1) = 32 sont possibles, et tous ceux au-delà.

Où apparaît-il ?

Il décrit le problème des nuggets, où des lots de 6, 9 et 20 ne peuvent pas former certains nombres, les timbres et l’affranchissement, la monnaie et le plus grand total inatteignable dans des problèmes d’ordonnancement. Pour trois valeurs ou plus, il n’y a pas de formule fermée simple, et des algorithmes sont nécessaires.

Ce calculateur vous a-t-il été utile ?

Merci pour votre avis !

Résultats indicatifs fournis à titre d'information. Ils ne remplacent pas l'avis d'un professionnel.