Problème des pièces de monnaie

Fichier:2 centimes face commune 1 et 2.png

Avec des pièces de 2 et de Modèle:Unité, on peut exprimer tout montant, sauf 1 et Modèle:Unité.

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 du nom du 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 monnaie de valeurs faciales fixées. 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). 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-difficileModèle:Refm.

Énoncé

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

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

La condition que les nombres $a_1,a_2,\dots ,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,\dots ,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.

Nombres de Frobenius pour n petit

Une formule existe pour $n=1$ et $n=2$. Aucune formule explicite générale n'est connue pour des valeurs plus grandes, problème que Frobenius mentionnait souvent dans ses coursModèle:,.

n = 1

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

n = 2

Modèle:Voir Le nombre de Frobenius d'une paire d'entiers $a,b>0$ premiers entre eux est : Modèle:IndenteDémonstration. Soit $m$ un entier arbitraire. Comme $a$ et $b$ sont premiers entre eux, d'après le théorème de Bachet-Bézout, il existe un unique 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 ou nuls) est que, pour ce couple particulier $(r,s)$, le coefficient $r$ soit, comme $s$, positif ou nul. Ce n'est pas le cas si $m=ab-a-ab=-a+(a-1)b$ auquel cas $r=-1,s=a-1$ d'après l'unicité, mais c'est le cas dès que $m⩾ab-a-b+1=(a-1)(b-1)$ puisqu'alors, $ra=m-sb⩾(a-1)(b-1)-(a-1)b=-a+1$, soit $(r+1)a⩾1$, d'où $r+1>0$, et $r⩾0$.

Ce résultat se déduit aussi simplement du lemme suivant :

LEMME : si deux entiers relatifs ont pour somme $ab-a-b$ alors un et exactement un seul est "représentable".

En effet, 0 étant représentable, $ab-a-b$ ne l'est donc pas; et si $m>ab-a-ab$, $ab-a-ab-m<0$ n'est pas représentable, donc $m$ l'est.

Ce théorème fait partie de ceux du folklore mathématique dont on ne connaît pas le découvreur. Il est extrêmement souventModèle:, attribué par erreur à James Joseph Sylvester en 1884, alors qu'il le considérait sans doute comme connu et que sa publication consistait en un autre exercice, que l'on peut dès lors reformuler ainsi : démontrer que Modèle:RetraitCette propriété se déduit du lemme précédent car si $A_1$ est l'ensemble des nombres de 0 à $g(a,b)$ qui sont représentables, et $A_2$ celui de ceux qui ne le sont pas, l'application $m\mapsto g(a,b)-m$ définit une bijection de $A_1$ sur $A_2$.

n = 3

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), 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 montrent que la minoration de Davison,

$g(a_1,a_2,a_3)⩾\sqrt{3a_1{a}_2{a}_3}-a_1-a_2-a_3,$

est assez fine.

Dans le cas où $a_1=ab,a_2=bc,a_3=ca$ où $a,b,c$ sont trois entiers strictement positifs premiers entre eux deux à deux, le nombre de Frobenius est connuModèle:, :

$g(ab,bc,ca)=2abc-ab-bc-ca$.

Nombres de Frobenius pour des ensembles particuliers

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

Cas d'entiers premiers deux à deux

Si $a_1,a_2,\cdots ,a_n$ sont des entiers strictement positifs deux à deux premiers entre eux, alors

$g(\frac{\pi }{a_1},\frac{\pi }{a_2},\dots ,\frac{\pi }{a_n})=\pi (n-1-\sum _{i=1}^n\frac{1}{a_i})$ où $\pi =a_1\cdots a_n$.

Suites arithmétiques

Un formule simple existe pour des entiers en progression arithmétique. Étant donné trois entiers strictement positifs $a,d,s$, avec $\mathrm{pgcd}(a,d)=1$, on a :

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

Par exemple, les suites $(g(n,n+1,\dots ,n+k){)}_n$ pour $k=2,\dots ,8$ sont répertoriées dans l'OEIS : Modèle:OEIS2C , Modèle:OEIS2C, Modèle:OEIS2C, Modèle:OEIS2C, Modèle:OEIS2C, Modèle:OEIS2C, Modèle:OEIS2C.

Suites géométriques

De même, il existe une formule explicite pour un cas particulier d'entiers en progression géométrique. Étant donné trois entiers strictement positifs $m,n,k$, avec $\mathrm{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

Nombres Modèle:Lang

Modèle:Lang dans une boîte de 20.

Erreur lors de la création de la vignette :

Solution graphique au problème des Modèle:Lang. 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 Modèle:LangModèle:, est un cas particulier du problème des pièces de monnaie.

Un nombre $n$ est dit Modèle:Lang si l'on peut, en choisissant bien ses boîtes de Modèle:Lang, parvenir à un total de $n$ Modèle:Lang. Les boîtes classiques contiennent 6, 9 ou 20 Modèle:Lang. 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 Modèle:Lang — 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 Modèle:Lang est 43 :

• tous les entiers à partir de 44 sont des nombres Modèle:Lang 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 Modèle:Lang : on ne peut pas obtenir 43 Modèle:Lang 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 Modèle:Lang restants ne forment pas un multiple de 3. Enfin, en prenant deux boîtes de 20, il reste 3 Modèle:Lang.

On peut en outre vérifier de même que parmi les 44 nombres de 0 à 43, la moitié ne sont pas des nombres Modèle:Lang (leur liste est la Modèle: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 Modèle:Lang de 4 Modèle:Lang, le plus grand nombre qui n'est pas Modèle:Lang descend à 11.
• Dans certains pays où la boîte de 9 Modèle:Lang est remplacée par une boîte de 10, on ne peut obtenir qu'un nombre pair de Modèle:Lang, si bien qu'aucun nombre impair n'est un nombre Modèle:Lang.

D'autres exemples

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.

Voir aussi

Articles connexes

• Modèle:Lien
• Modèle:Lien