Nombre Mc Nugget

Le problème de Frobenius ou des pièces de monnaies est une généralisation avec des barquettes de différentes tailles. Barquettes ou pièces de monnaie ou poids pour la pesée ou ...

Sommaire de cette page

>>> McNugget

>>> Cas de deux valeurs

>>> Problème de la ferme (ou de la ville de Hamlet)

>>> Le problème des pièces de monnaie

>>> Le problème du rendu de monnaie

>>> Le problème des timbres postaux

>>> Calculabilité

>>> Démonstration du théorème des McNugget

Débutants

Nombres

Glossaire

Nombres

Mc Nugget		haut
Le problème Le restaurant ne sert que des barquettes de Nuggets de 4, 6 ou 20 pièces. Est-il possible d'acheter n'importe combien de pièces ? Non, mais à partir d'une certaine quantité, c'est toujours possible. Quelle est la valeur limite ? Les quantités impossibles ne sont pas des nombres McNugget. La limite est appelé nombre de Frobenius.	Barquettes 6, 9 et 20 Nombres NON-McNugget 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43. Nombre de Frobenius: 43. En ajoutant une barquette de quatre nuggets, toutes les combinaisons sont possibles sauf 1, 2, 3, 5, 7 et 11.
Tableau des commandes possibles En colonne de droite, s est la quantité qu'il est possible de commander en combinant les boites de nuggets. La quantité minimale est 6; les nombres 1, 2, 3, 4 et 5 ne sont donc pas Mc Nugget. Idem pour les valeurs 7 et 8. Etc. À partir de 44, toutes les valeurs de s sont possibles. Partitions On a ainsi les partions possibles du nombre s avec les nombres 6, 9 et 20. Certaines partitions sont multiples comme: 18 = 6 + 6 + 6 = 9 + 9 (double partitions). Il s'agit de deux partitions particulières parmi les 385 possibles pour le nombre 18. Formule des nombres MC Nuggets N = 6x + 9y + 20z

Voir Brève 49-968

Cas de deux valeurs avec exemples

haut

Le théorème des Chicken McNugget ou problème du timbre-poste ou problème de la pièce de Frobenius.

Pour deux entiers positifs premiers entre eux m et n, le plus grand entier qui ne peut pas être écrit sous la forme am + bn pour les entiers non négatifs a, b est mn – m – n.

Une conséquence du théorème est qu'il existe exactement:

entiers positifs qui ne peuvent pas être exprimés sous la forme am + bn.

Démonstration

La preuve est présentée in fine (*niveau supérieur).

Montré en 1884 par James Sylvester.

Origine la plus populaire

À l'origine, McDonald's vendait ses nuggets en boites de 9 et 20.

Sachant cela, les férus de maths ont vite calculé le plus grand nombre de nuggets qui n'aurait pas pu être achetées avec ces packs. Dans ce cas c'est 151.

9 x 20 – 9 – 20 = 151

La société a vite ajouté des barquettes de 4 pièces.

Le théorème des Chicken McNugget est aussi appelé: problème des pièces de monnaie de Frobenius ou problème de Frobenius. Le mathématicien allemand Ferdinand Frobenius (1849-1917) s'est enquis de la plus grande valeur qui n'aurait pas pu être atteinte avec certains types de pièces.

Autres exemples

Le peintre achète sa peinture en pots de 2 ou 7 litres. Quelle est la plus grande quantité que le peintre ne peut pas obtenir ?

2 × 7 – 2 – 7 = 5

Au football américain, on compte 3 points pour un essai et 7 points pour un essai transformé. Quel est le plus grand score qui ne sera pas plausible pour un match ?

3 × 7 – 3 – 7 = 11

Nombres 2-McNugget jusqu'à 100

Nombres de la forme mn – m – n avec m et n premiers entre eux.

Exemple m = 3 et n = 8 (qui sont premiers entre eux):
mn – m – n = 24 – 11 = 13

OUI de la forme mn – m – n

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 47, 49, 51, 53, 55, 59, 63, 65, 67, 69, 71, 79, 83, 89, 95, 97.

NON (hors tous les nombres pairs)

21, 33, 45, 57, 61, 73, 75, 77, 81, 85, 87, 91, 93, 99.

Problème de la ferme (ou de la ville de Hamlet)

Problème

Cette ferme compte 3 personnes par cheval, 4 moutons par vache et 3 canards par personne.

Quel est le total de personnes, de chevaux, de moutons, de vaches et de canards qui ne pourra jamais être atteint ?

Solution

Le problème des pièces de monnaie

haut

Il s'agit de déterminer le montant le plus élevé que l'on ne peut pas représenter en n'utilisant que des pièces de monnaie de valeurs faciales fixées.

Ou plus généralement des nombres donnés, valeurs des pièces ou autres, comme des poids pour la pesée.

Les valeurs sont première entre elles (PGCD = 1).

Le tableau montre quelques exemples de types de barquettes (a, b et c) et indique en colonne de gauche (s) la limite telle qu'au-delà, il est possible de commander n'importe quelle quantité.

Exemple

Aves des barquettes de 2 et 3 pièces, toutes les combinaisons supérieures à 1 sont possibles.

Avec des barquettes de 7 et 13 pièces, il faut atteindre 71 pour que les valeurs suivantes soient toutes atteignables.
Son calcul est 7 × 13 – 7 – 13 = 71

S	a	b	c
1	2	3
5	3	4
2	3	4	6
7	3	5
4	3	5	7
23	5	7
13	5	7	11
29	6	7
17	6	7	8
43	6	9	20
49	6	10	20
49	6	11
48	7	11
30	7	11	13
71	7	13
45	7	13	23

Anglais: Coin problem

Le problème du rendu de monnaie

haut

Étant donnée une somme (s) à payer quelle est le minimum de pièces ou billets pour rendre la monnaie.

C'est à nouveau un problème de partition: quelle est la partition de s minimale avec des nombres donnés.

Ce problème est identique au précédent avec s = somme à rendre à l'acheteur.

Notre expérience de tous les jours semble montrer que la résolution de ce problème est simble. Pas toujours le cas pour de grandes valeurs !

Exemple 1

Prix: 14 euros

Paiement: billet de 20 euros

Pièces disponibles:1, 2, 5 euros

Monnaie rendue: 6 = 5 + 1 ou 2 + 2 + 2 = 1 + 1 + 1 + 1 + 1 + 1.

Minimum: 5 euros et 1 euro.

Exemple 2

9,34 euros pour 10.

À rendre: 66 cts = 50 + 10 + 5 + 1

Le problème des timbres postaux

haut

Énigme mathématique

Quelle est la plus petite valeur d'affranchissement qui ne peut pas être placée sur une enveloppe, si

celle-ci ne peut contenir qu'un nombre limité de timbres, et

ceux-ci ne peuvent avoir que certaines valeurs faciales spécifiées.

Formulation mathématique

Étant donné un entier m et un ensemble V d'entiers positifs, trouver le plus petit entier z qui ne peut pas être écrit comme la somme v₁ + v₂ + ··· + v_k d'un certain nombre k ≤ m d'éléments (pas nécessairement distincts) de V.

Exemple

L'enveloppe ne peut contenir que trois timbres et les valeurs de timbre disponibles soient 1 cent, 2 cents, 5 cents et 20 cents.

Alors la solution est de 13 cents; puisque toute valeur inférieure peut être obtenue avec au plus trois timbres (par exemple 4 = 2 + 2, 8 = 5 + 2 + 1, etc.).

Mais pour obtenir 13 cents, il faut utiliser au moins quatre timbres.

Voir Pliage de timbres

Calculabilité

Pour deux valeurs de pièces, il existe une formule de calcul du nombre de Frobenius, mais aucune pour plus de deux valeurs.

En revanche, il existe un algorithme qui calcule le nombre de Frobenius en temps polynomial, à condition de connaitre les valeurs des pièces données à priori (algorithme glouton).

Pas possible dans le cas général de valeurs de pièces données comme variables. Le problème est dit NP-difficile.

English corner

The Chicken McNugget theorem, also known as the Frobenius coin problem, states that for any two relatively prime integers m and n, the largest integer that cannot be expressed in the form am + bn for non-negative integers a and b is mn − m − n.

In other words, if I have boxes of 6 and 11 chicken nuggets, the largest number of chicken nuggets that is non-purchasable with a combination of these boxes is 6 × 11 − 6 − 11 = 49. Any number of chicken nuggets above 49 is purchasable.

Voir Anglais pour le bac et pour les affaires

Démonstration du théorème des McNugget*

haut

Théorème des McNugget :

Pour des entiers positifs premiers entre eux a et b, le nombre M = ab – a – b ne peut pas être exprimé sous la forme ax + by pour tous les entiers non négatifs x et y. De plus, tout entier n > M peut être représenté par ax + by pour certains entiers non négatifs x et y.

Principe

Il existe des nombres qui sont atteints et d'autres non-atteints avec deux nombres a et b.

Deux volets à la démonstration:

1 – prouver que M = ab – a – b est non atteint

2 – prouver que tout nombre supérieur à M est atteint:

*Cas 1*	M = ab – a - b	n'est pas atteint
*Preuve par contradiction: hypothèse*	Si M = ab – a – b	est atteint
*Alors il existe x et y*	ab – a – b	= ax + by
*En mod a (reste de la division par a = by)*	ax + by	≡ by mod a
*De manière semblable*	ab – a – b	≡ -b mod a
*En reprenant l'égalité*	by mod a	≡ -b mod a
*Or a et b sont premiers entre eux, il existe un inverse de b mod a (b'). En multipliant pa b'*	bb'y mod a	≡ -bb' mod a
		≡ (-1) × bb mod a
*En simplifiant*	y mod a	≡ -1
*Même raisonnement en divisant par b*	x mod b	≡ -1
*Les nombres a et b sont positifs. D'où les plus petites valeurs positives(en ajoutant une fois ou plus le diviseur à chacun)*	x y	≥ b – 1 ≥ a – 1
*Reprenons notre égalité supposée*	ab – a – b	= ax + by
*et appliquons les inégalités*		≥ a (b – 1) + b (a – 1) ≥ 2ab – a – b ≥ ab – a – b
*Contradiction ! L'hypothèse est fausse*	ab – a – b	≥ ab – a – b n

*Cas 2*	∀ M > ab – a - b	est atteint
*Preuve basée sur l'identité de Bézout*	Si a et b sont des entiers, il existe deux entiers x et y tels que:	ax + by = PGCD (a, b)
*Dans notre cas, a et b sont premiers entre eux*	PGCD (a , b) = 1	=> ∃ (x, y) : ax + by = 1
*Soit x' = nx et y' = ny*		ax' + by' = n
Si	x' et y'	solution de ax' + by' = n
*Alors*	x' – kb et y' + ka	aussi solution
*On choisit k pour que x' – kb soit entre 0 et b – 1 pour une valeur de k que l'on note k'*	0 ≤ x' – kb ≤ b – 1
*Notons les valeurs correspondantes de x et y*	x" = x' – k'b	y" = y' + k'a
*Or selon Bézout, ces nombres sont solutions*	x" et y"	solution de ax + by = n n
*Il reste à montrer que x" et y" ne sont pas négatifs.*
*x" l'est par définition*	Cf: 0 ≤ x" ≤ b – 1
*Ce que nous savons*	ax" + by" = n	et n > ab – a – b
*En rapprochant ces inégalités*	ax" + by" by" + b b(y" + 1)	> ab – a – b > ab –a – ax" > a(b – 1 – x")
*Or, on sait que*	x" b – 1 – x"	≤ b – 1 ≥ 0
*En multipliant par a qui est positif*	a (b – 1 – x")	≥ 0
*Remplacement par une quantité plus grande*	b (y" + 1)	≥ 0
*Or b est positif*	y" + 1 y"	≥ 0 ≥ 0 n

Référence: The Chicken McNugget Theorem, Explained – Mike Beneschan

Haut de page (ou double-clic)

Retour	Pesée avec des 4 et des 7
Suite	Pesée des 9 billes Pesée des douze billes Nombres premiers et raison (progression arithmétique) Problème du sac à dos Permutations conduisant à total fixé Problème impossible de la somme et du produit (Freudenthal)
Voir	Énigmes de transvasements Énigmes en économie Jeux, énigmes – Index Partage – Énigmes classiques
Sites	Problème des pièces de monnaie – Wikipédia McNugget Number – Wolfram MAthWorld OEIS A065003 – Not McNugget numbers Chicken McNugget Theorem – Xavier Lien Chicken McNugget Theorem – AoPSOnLine 2015 AMC 10B Problems/Problem 15 – AoPSOnLin Factoring in the Chicken McNugget Monoid - Scott T. Chapman & Chris O'Neil**
Vidéo	How to order 43 Chicken McNuggets – Numberphile – Video Youtube
Cette page	http://villemin.gerard.free.fr/aJeux1/Pesee/Nugget.htm