Problème des pièces de monnaie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Problème du rendu de monnaie.
Avec des pièces de 2 et de 5 centimes, on peut exprimer tout montant, sauf 1 et 3 centimes.

En mathématiques, le problème des pièces de monnaie, également appelé le problème des pièces de Frobenius ou le problème de Frobenius d'après le mathématicien Georg Frobenius, est un problème diophantien linéaire. 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 monnaies de valeurs faciales fixées[1]. Par exemple, le plus grand montant que l'on ne peut pas exprimer avec des pièces de 3 et de 5 unités est 7 unités. La solution du problème pour un ensemble de pièces donné est appelée le nombre de Frobenius de cet ensemble.

Il existe une formule explicite pour le nombre de Frobenius dans le cas où il n'y a que deux valeurs de pièces. Si le nombre de valeurs est plus grand, on ne connaît pas de formule explicite ; toutefois, pour tout nombre fixé de valeurs faciales, il existe un algorithme qui calcule le nombre de Frobenius en temps polynomial (en fonction du logarithme des valeurs faciales données en entrée)[2]. On ne connaît pas d'algorithme polynomial comme fonction du nombre de valeurs faciales, et le problème général, où le nombre de valeurs faciales est arbitrairement grand, est NP-difficile[3],[4].

Énoncé[modifier | modifier le code]

En termes mathématiques, le problème s'énonce comme suit.

Étant donnés des entiers strictement positifs a_1,a_2,\ldots, a_n distincts et premiers entre eux dans leur ensemble, déterminer le plus grand entier qui n'est pas une combinaison linéaire à coefficients entiers positifs de ces entiers, c'est-à-dire qui n'est pas de la forme k_1a_1+k_2a_2+\cdots+k_na_n pour des entiers positifs k_1,k_2,\ldots,k_n.

Ce plus grand entier est appelé le nombre de Frobenius de l'ensemble \{a_1,a_2,\ldots,a_n\} et est noté habituellement g(a_1,a_2,\ldots,a_n).

La condition que les nombres a_1,a_2,\ldots, a_n soient premiers entre eux, c'est-à-dire que leur PGCD d soit égal à 1, est nécessaire et suffisante pour assurer l'existence du nombre de Frobenius :

  • toute combinaison linéaire de ces entiers est divisible par d, donc un entier qui n'est pas multiple de d ne peut pas être exprimé de cette manière or, lorsque d > 1, il n'existe pas de plus grand entier non multiple de d (par exemple, si toutes les valeurs faciales sont paires, on ne peut pas exprimer un montant impair) ;
  • au contraire, si d = 1, tout entier m est combinaison linéaire à coefficients entiers de a_1,a_2,\ldots, a_n et même, si m est assez grand, à coefficients entiers positifs, d'après un théorème de Schur. Dans ce cas, le nombre de Frobenius existe[5].

Nombres de Frobenius pour n petit[modifier | modifier le code]

Une formule existe pour n = 1 et n = 2. Aucune formule explicite générale n'est connue pour des valeurs plus grandes[4], problème que Frobenius mentionnait souvent dans ses cours[6],[7].

n = 1[modifier | modifier le code]

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

n = 2[modifier | modifier le code]

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 ≤ sa – 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.

n = 3[modifier | modifier le code]

On connaît des algorithmes rapides pour le calcul du nombre de Frobenius de trois entiers a_1, a_2, a_3 (détaillés dans demi-groupe numérique (en)), 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],

g(a_1, a_2, a_3) \geq \sqrt{3a_1a_2a_3} - a_1 - a_2 - a_3,

est assez fine.

Nombres de Frobenius pour des ensembles particuliers[modifier | modifier le code]

La formule ci-dessus pour n = 2 se généralise de deux façons.

Suites arithmétiques[modifier | modifier le code]

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

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.

Suites géométriques[modifier | modifier le code]

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 m, n, k, avec \operatorname{pgcd}(m,n)=1, on a :

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}.

Exemples élémentaires[modifier | modifier le code]

Nombres McNugget[modifier | modifier le code]

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.

D'autres exemples[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Coin Problem » (voir la liste des auteurs).

  1. (en) Jorge L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Univ. Press, coll. « Oxford Lecture Series in Mathematics and its Applications » (no 30),‎ .
  2. (en) Ravi Kannan, « Lattice translates of a polytope and the Frobenius problem », Combinatorica, vol. 12, no 2,‎ , p. 161-177 (DOI 10.1007/BF01204720).
  3. (en) D. Beihoffer, J. Hendry, A. Nijenhuis (en) et S. Wagon (en), « Faster algorithms for Frobenius numbers », Electronic Journal of Combinatorics, vol. 12,‎ , R27 (lire en ligne).
  4. a et b (en) Eric W. Weisstein, « Coin Problem », MathWorld.
  5. a, b et c Dans le cas trivial où l'un des entiers vaut 1, tout entier naturel est représentable donc le nombre de Frobenius — le plus grand entier relatif non représentable — est –1.
  6. (en) Alfred Brauer, « On a Problem of Partitions », Amer. J. Math., vol. 64, no 1,‎ , p. 299-312 (JSTOR 2371684).
  7. (en) Alfred Brauer et James E. Shockley, « On a problem of Frobenius », J. Reine Angew. Math., vol. 211,‎ , p. 215-220 (lire en ligne).
  8. a, b et c (en) Matthias Beck et Sinai Robins, Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra, Springer,‎ (lire en ligne), chap. 1 (« The Coin-Exchange Problem of Frobenius »), p. 16.
  9. (en) Zdzisław Skupień (en), « A generalization of Sylvester's and Frobenius' problems », Acta Arithmetica, vol. 65, no 4,‎ , p. 353-366 (lire en ligne).
  10. (en) J. J. Sylvester, « [Question] 7382 (Solution by W. J. Curran Sharp) », Mathematical Questions from the Educational Times, vol. 41,‎ , p. 21 (lire en ligne).
  11. Cas particulier d'un théorème de J. J. Sylvester, « Théorie des nombres », Comptes rendus hebdomadaires des séances de l'Académie des sciences, vol. 50, no 1,‎ , p. 367 (lire en ligne) cité dans (en) Leonard Eugene Dickson, History of the Theory of Numbers (en) [détail des éditions], vol. II, chap. 2, p. 66.
  12. Pour une formulation plus fidèle à Sylvester 1884 et une démonstration différente, voir « Théorème de Cesàro » dans l'article détaillé.
  13. Ou encore : de 1 à (a – 1)(b – 1), cf. Beck et Robins 2007, p. 6.
  14. (en) M. Beck et S. Zacks, « Refined upper bounds for the linear Diophantine problem of Frobenius », Adv. Appl. Math., vol. 32, no 3,‎ , p. 454-467 (DOI 10.1016/S0196-8858(03)00055-1, arXiv math/0305420).
  15. (en) J. L. Davison, « On the Linear Diophantine Problem of Frobenius », Journal of Number Theory, vol. 48, no 3,‎ , p. 353-363 (DOI 10.1006/jnth.1994.1071).
  16. Ramírez Alfonsín 2005, p. 59-69.
  17. (en) Darren C. Ong et Vadim Ponomarenko, « The Frobenius Number of Geometric Sequences », INTEGERS: the Electronic Journal of Combinatorial Number Theory, vol. 8 « A33 »,‎ (lire en ligne).
  18. (en) Anita Wah et Henri Picciotto, Algebra : Themes, Tools, Concepts,‎ (lire en ligne), « Lesson 5.8 Building-block Numbers », p. 186.
  19. (en) Eric W. Weisstein, « McNugget Number », MathWorld.
  20. (en) Brady Haran (en), How to order 43 Chicken McNuggets - Numberphile « Comment commander 43 croquettes de poulet ».

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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