Problème des pièces de monnaie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Avec des pièces de 2 et de 5 centimes, on peut exprimer tout montant, sauf 1 et 3 centimes.

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 Ferdinand Frobenius, est un problème mathématique. Il s'agit déterminer le montant le plus élevé l'on ne peut pas représenter en 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ée est appelé 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. Si le nombre de valeurs de pièces est plus grand, on ne connaît pas de formule explicite; toute fois, 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é des entiers positifs a_1,a_2,\ldots, a_n premiers entre eux dans leur ensemble, déterminer le plus grand entier qui n'est pas une combinaison linéaire à coefficients entiers positifs ou nuls 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 ou nuls 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 sont premiers entre eux est nécessaire pour assurer l'existence du nombre de Frobenius. Toute combinaison linéaire de ces entiers est divisible par leur pgcd, donc un entier qui n'est pas multiple de ce pgcd ne peut pas être exprimé de cette manière, et il n'en existe pas de plus grand. Par exemple, si toutes les valeurs faciales sont paires, on ne peut pas exprimer un montant impair. Au contraire, si les nombres a_1,a_2,\ldots, a_n sont premiers entre eux, tout nombre assez grand est combinaison linéaire à coefficients positifs ou nuls de ces entiers; ceci résulte d'un théorème de Schur. Dans ce cas, le nombre de Frobenius existe.

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

Une formule existe pour n=1 et n=2. Aucune forme close n'est connue pour des valeurs plus grandes[4].

n = 1[modifier | modifier le code]

Dans ce cas, l'unique valeur faciale est nécessairement 1, et tout entier en est multiple : il n'y a pas de nombre de Frobenius.

n = 2[modifier | modifier le code]

Pour n=2, , le nombre de Frobenius d'un ensemble de deux entiers \{a, b\} est donné par la formule g(a,b)=ab-a-b. Cette formule a été découverte publiée par James Joseph Sylvester en 1884[5]. Sylvester montre aussi que, dans ce cas, il y a exactement (a-1)(b-1)/2 entiers qui ne sont pas représentables.

Une autre expression pour g(a,b) est donnée par Skupień[6] : Si a et b sont des entiers positifs premiers entre eux, alors pour tout entier n \ge (a-1)(b-1), il existe une paire unique d'entiers non négatifs (r, s) telle que n = r a + s  b et s < a.

Démonstration. Pour j=0,1,\ldots,a-1 , les entiers n - j b sont deux-à-deux distincts modulo a, parce que a et b sont premiers entre eux. Il existe donc exactement un j, soit j=s, tel que n = r a +s b, avec r \ge 0 parce que r a = n - s b \ge (a-1)(b-1) - (a -1)b = -a + 1.

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. Des bornes inférieures et supérieures pour les nombres de Frobenius de trois entiers sont connues. Une borne inférieure, due à Davidson, est

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

Cette borne est réputée être assez précise[7].

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

Suites arithmétiques[modifier | modifier le code]

Un formule simple existe pour des ensembles d'entiers d'une suite arithmétique[8]. É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 close pour les nombres de Frobenius d'un ensemble d'entiers en suite géométrique[9]. É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]

Solution graphique au problème de 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.
McDonald's Chicken McNuggets dans une boîte de 20.

Un cas particulier du problème des pièces de monnaie est aussi appelé le problème des nombres McNugget. Cette version du problème de Frobenius est présentée dans le manuel d'algèbre d'Anita Wah et Henri Picciotto[10]. Un nombre McNugget est le nombre total de Chicken McNuggets présents dans un ensemble de boîtes de croquettes. Les boîtes originales, avant l'introduction des boîtes Happy Meal, contiennent 6, 9, ou 20 croquettes. D'après le théorème de Schur, comme 6, 9, et 20 sont des nombres premiers entre eux, tout nombre assez grand peut être exprimé comme combinaison linéaire à coefficients positifs ou nuls de ces trois nombres. Il existe donc un plus grand nombre qui n'est pas une nombre McNugget - et c'est le nombre de Frobenius de 6, 9 et 20 -, et tous les nombres plus grands sont des nombre McNugget. Les entiers exceptionnels, qui ne sont pas des nombres McNugget, sont :

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, et 43. (C'est la suite suite A065003 de l'OEIS.)

Le plus grand entier qui n'est pas un nombre de McNugget est donc 43[11]. Pour voir directement que tous les nombres plus grands que 43 sont des nombres McNugget, on peut considère les six partitions suivantes :

 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 

Tout entier plus grand s'obtient en additionnant une certain nombre de 6 à l'une de ces partitions. On peut aussi vérifier directement que 43 n'est pas un nombre McNugget. D'abord, on ne peut obtenir 43 croquettes selement avec des boîtes de 6 et 9 car le résultat est un multiple de 3. Si on prend une seule boîte de 20, on ne peut faire mieux parce les 23 croquettes restantes ne sont pas multiples de 3. Enfin, en prenant deux boîtes de 20, il reste 3 croquettes.

Depuis l'introduction d'une boîte Happy-Meal de quatre croquettes, le plus grand nombre qui n'est pas McNugget descend à 11. Dans certains pays où la boîte de 9 croquettes est remplacée par une boîte de 10, on ne peut obtenir qu'un nombre pair de croquettes, et aucun nombre impair 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, dans les football américain, tout résultat est possible dans une partie ordinaire sauf 1 point.

Articles connexes[modifier | modifier le code]

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

  1. Jorge L. Ramírez Alfonsín, The Diophantine Frobenius problem, Oxford Univ. Press, coll. « Oxford Lecture Series in Mathematics and its Applications » (no 30),‎ 2005.
  2. Ravi Kannan, « Lattice translates of a polytope and the Frobenius problem », Combinatorica, vol. 12, no 2,‎ 1992, p. 161–177 (DOI 10.1007/BF01204720).
  3. D. Beihoffer, J. Hendry, A. Nijenhuis et S. Wagon, « Faster algorithms for Frobenius numbers », Electronic Journal of Combinatorics, vol. 12,‎ 2005, R27 (lire en ligne).
  4. a et b (en) Eric W. Weisstein, « Coin Problem », MathWorld.
  5. James Joseph Sylvester, « Question 7382 », Mathematical Questions from the Educational Times, vol. 41,‎ 1884, p. 21 (lire en ligne).
  6. Zdzisław Skupień, « A generalization of Sylvester’s and Frobenius’ problems », Acta Arithmetica, vol. 65, no 4,‎ 1993, p. 353–366 (lire en ligne).
  7. M. Beck et S. Zacks, « Refined upper bounds for the linear Diophantine problem of Frobenius », Adv. Appl. Math., vol. 32, no 3,‎ 2004, p. 454–467 (DOI 10.1016/S0196-8858(03)00055-1, arXiv math/0305420).
  8. Ramírez Alfonsín 2005, p. 59-69.
  9. Darren C. Ong et Vadim Ponomarenko, « The Frobenius Number of Geometric Sequences », INTEGERS: the Electronic Journal of Combinatorial Number Theory, vol. 8 « A33 »,‎ 2008 (lire en ligne).
  10. Anita Wah et Henri Picciotto, Algebra : Themes, Tools, Concepts,‎ 1994 (lire en ligne), « Lesson 5.8 Building-block Numbers », p. 186
  11. (en) Eric W. Weisstein, « McNugget Number », MathWorld.

(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)

Lien externe[modifier | modifier le code]