Problème des pièces de monnaie

Dans ce cas, l'unique valeur faciale est nécessairement 1 donc[5] le nombre de Frobenius vaut –1.

Le nombre de Frobenius d'une paire d'entiers a, b > 0 premiers entre eux est : g(a, b) = ab – a – b = (a – 1)(b – 1) – 1[5].

Démonstration. Soit m un entier arbitraire. Comme a et b sont premiers entre eux, il existe exactement un couple (r, s) d'entiers relatifs tels que m = ra + sb et 0 ≤ s ≤ a – 1. La condition pour que m soit « représentable » (par deux entiers positifs) est que, pour ce couple particulier (r, s), le coefficient r soit, comme s, positif. Ce n'est pas le cas si m = –a + (a – 1)b, mais c'est le cas dès que m ≥ –a + (a – 1)b + 1 = (a – 1)(b – 1) puisqu'alors, ra = m – sb ≥ (a – 1)(b – 1) – (a – 1)b = –a + 1.

Cette formule fait partie des théorèmes du folklore mathématique (en) dont on ne connaît pas le découvreur[8]. Elle est extrêmement souvent[8] - [9] attribuée par erreur à James Joseph Sylvester en 1884[10], alors qu'il la considérait sans doute comme connue[8] et que sa publication consistait en un autre exercice[11], que l'on peut dès lors reformuler[12] ainsi : démontrer que parmi les entiers de 0 à g(a, b)[13], exactement la moitié sont représentables.

On connaît des algorithmes rapides pour le calcul du nombre de Frobenius de trois entiers ${\displaystyle a_{1},a_{2},a_{3}}$ (détaillés dans demi-groupe numérique), même si les calculs peuvent être longs et pénibles quand on les effectue à la main. On connaît des minorants et des majorants pour les nombres de Frobenius de trois entiers. Des données expérimentales[14] montrent que la minoration de Davison[15],

${\displaystyle g(a_{1},a_{2},a_{3})\geq {\sqrt {3a_{1}a_{2}a_{3}}}-a_{1}-a_{2}-a_{3},}$

est assez fine.

Un formule simple existe pour des ensembles d'entiers d'une suite arithmétique[16]. Étant donné trois entiers ${\displaystyle a,d,s}$, avec ${\displaystyle \operatorname {pgcd} (a,d)=1}$, on a :

${\displaystyle g(a,a+d,a+2d,\dots ,a+sd)=\left(\left\lfloor {\frac {a-2}{s}}\right\rfloor +1\right)a+(d-1)(a-1)-1.}$

De même, il existe une formule explicite pour les nombres de Frobenius d'un ensemble d'entiers en suite géométrique[17]. Étant donné trois entiers ${\displaystyle m,n,k}$, avec ${\displaystyle \operatorname {pgcd} (m,n)=1}$, on a :

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}$

McDonald's Chicken McNuggets dans une boîte de 20.

Solution graphique au problème des McNuggets. Une ligne bleue (resp. rouge) désigne une quantité qui peut être achetée ou au contraire, qui ne peut pas l'être. La plus haute ligne rouge est pour 43.

Le problème des nombres McNugget[18] - [19] est un cas particulier du problème des pièces de monnaie.

Un nombre n est dit McNugget si l'on peut, en choisissant bien ses boîtes de Chicken McNuggets, parvenir à un total de n nuggets. Les boîtes classiques contiennent 6, 9 ou 20 nuggets. D'après un théorème de Schur, comme 6, 9 et 20 sont premiers entre eux dans leur ensemble, tout entier « assez grand » peut être exprimé comme combinaison linéaire à coefficients entiers positifs de ces trois nombres. Autrement dit : il existe un plus grand nombre qui n'est pas un nombre McNugget — c'est le nombre de Frobenius de l'ensemble {6, 9, 20}.

Mais on peut expliciter complètement cet exemple, sans invoquer le théorème de Schur, en démontrant directement que le plus grand entier qui n'est pas un nombre McNugget est 43 :

• tous les entiers à partir de 44 sont des nombres McNugget car

44 = 6 + 9 + 9 + 20	45 = 9 + 9 + 9 + 9 + 9	46 = 6 + 20 + 20
47 = 9 + 9 + 9 + 20	48 = 6 + 6 + 9 + 9 + 9 + 9	49 = 9 + 20 + 20

et tout entier plus grand s'obtient en additionnant un certain nombre de 6 à l'une de ces partitions ;

• 43 n'est pas un nombre McNugget[20] : on ne peut pas obtenir 43 nuggets avec seulement des boîtes de 6 et 9 car le résultat est un multiple de 3. Si l'on prend une seule boîte de 20, on ne peut pas faire mieux parce que les 23 nuggets restants ne forment pas un multiple de 3. Enfin, en prenant deux boîtes de 20, il reste 3 nuggets.

On peut en outre vérifier de même que parmi les 44 nombres de 0 à 43, la moitié ne sont pas des nombres McNugget (leur liste est la suite A065003 de l'OEIS : 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 et 43) et trouver des partitions pour ceux de l'autre moitié (y compris pour 0, égal à la somme vide).

Variantes

• Depuis l'introduction d'une boîte Happy Meal de 4 nuggets, le plus grand nombre qui n'est pas McNugget descend à 11.
• Dans certains pays où la boîte de 9 nuggets est remplacée par une boîte de 10, on ne peut obtenir qu'un nombre pair de nuggets, si bien qu'aucun nombre impair n'est un nombre McNugget.

En rugby à XV, il y a quatre types de points : le but (3 points), le drop (3 points), l'essai (5 points) et l'essai transformé (7 points). En combinant ces valeurs, tout total est possible sauf 1, 2 et 4.

De même, au football américain, tout résultat est possible dans une partie ordinaire sauf 1 point.

• Problème des timbres-poste (en)
• Sylver coinage (en)

Jean-Paul Allouche, « Pièces et billets », sur images des Maths, 9 octobre 2009