Voir la source de Problème des pièces de monnaie

{{Confusion|Problème du rendu de monnaie}}
[[Fichier:2_centimes_face_commune_1_et_2.png|vignette|upright=0.8|Avec des pièces de 2 et de {{unité|5|centimes}}, on peut exprimer tout montant, sauf 1 et {{unité|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''' du nom du [[mathématicien]] [[Georg Frobenius]], est un problème [[Équation diophantienne|diophantien]] [[Équation linéaire|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<ref name=ramirez/>. 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 [[Algorithmique|algorithme]] qui calcule le nombre de Frobenius en [[Théorie de la complexité (informatique théorique)|temps polynomial]] (en fonction du logarithme des valeurs faciales données en entrée)<ref name=kannan/>. 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]]{{refm|FF|mw}}.

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

{{Énoncé|Étant donnés des [[entier naturel|entiers]] [[Nombre positif|strictement positifs]] <math>a_1,a_2,\ldots, a_n</math> distincts et [[Nombres premiers entre eux#Extension à n nombres|premiers entre eux dans leur ensemble]], déterminer le plus grand entier qui n'est pas une [[combinaison linéaire]] à coefficients [[entier naturel|entiers positifs ou nuls]] de ces entiers, c'est-à-dire qui n'est pas de la forme {{indente|<math>k_1a_1+k_2a_2+\cdots+k_na_n</math>}} pour des entiers positifs ou nuls <math>k_1,k_2,\ldots,k_n</math>.
}}

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

La condition que les nombres <math>a_1,a_2,\ldots, a_n</math> soient premiers entre eux, c'est-à-dire que leur [[PGCD]] <math>d</math> soit égal à 1, est [[Condition nécessaire et suffisante|nécessaire et suffisante]] pour assurer l'existence du nombre de Frobenius :
* toute combinaison linéaire de ces entiers est [[divisible]] par <math>d</math>, donc un entier qui n'est pas [[Multiple (mathématiques)|multiple]] de <math>d</math> ne peut pas être exprimé de cette manière or, lorsque <math>d>1</math>, il n'existe pas de plus grand entier non multiple de <math>d</math> (par exemple, si toutes les valeurs faciales sont paires, on ne peut pas exprimer un montant impair) ;
* au contraire, si <math>d=1</math>, [[Théorème de Bachet-Bézout|tout entier ''m'' est combinaison linéaire à coefficients entiers]] de <math>a_1,a_2,\ldots, a_n</math> et même, si <math>m</math> est assez grand, à coefficients entiers ''positifs'', d'après [[Théorème de Schur#En combinatoire|un théorème de Schur]]. Dans ce cas, le nombre de Frobenius existe<ref name=Cas_trivial>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.</ref>.

== Nombres de Frobenius pour ''n'' petit ==
Une formule existe pour <math>n=1</math> et <math>n=2</math>. Aucune [[formule explicite]] générale n'est connue pour des valeurs plus grandes<ref name=mw/>, problème que Frobenius mentionnait souvent dans ses cours<ref name=Bra/>{{,}}<ref name=BraSho/>.

=== ''n'' = 1 ===
Dans ce cas, l'unique valeur faciale est nécessairement 1 donc<ref name=Cas_trivial/> le nombre de Frobenius vaut –1.

=== ''n'' = 2 ===
{{Voir|1=Équation diophantienne ax + by = c#Recherche de solutions dans l'ensemble des entiers naturels{{!}}§ « Recherche de solutions dans l'ensemble des entiers naturels » de l'article sur l'équation diophantienne ''ax + by = c''}}
Le nombre de Frobenius d'une [[paire]] d'entiers <math>a,b>0</math> premiers entre eux est :
{{indente|1=<math> g(a,b) = ab -a - b = (a - 1)(b - 1) - 1</math><ref name=Cas_trivial/>.}}''Démonstration.'' Soit <math>m</math> un entier arbitraire. Comme <math>a</math> et <math>b</math> sont premiers entre eux, d'après le [[théorème de Bachet-Bézout]], il existe un unique couple <math>(r, s)</math> d'[[entiers relatifs]] tels que <math>m = ra + sb</math> et <math>0 \leqslant s \leqslant a -1.</math> La condition pour que <math>m</math> soit « représentable » (par deux entiers positifs ou nuls) est que, pour ce couple particulier <math>(r, s)</math>, le coefficient <math>r</math> soit, comme <math>s</math>, positif ou nul. Ce n'est pas le cas si <math>m =ab-a-ab= -a + (a - 1)b</math> auquel cas <math>r=-1,s=a-1</math> d'après l'unicité, mais c'est le cas dès que <math>m \geqslant ab-a-b+1 = (a - 1)(b - 1)</math> puisqu'alors, <math>ra = m - sb \geqslant (a - 1)(b - 1) - (a - 1)b = -a + 1 </math>, soit <math>(r+1)a\geqslant1 </math>, d'où <math>r+1>0 </math>, et <math>r\geqslant0 </math>.

Ce résultat se déduit aussi simplement du lemme suivant<ref name="boyer">{{Ouvrage|langue=fr|auteur1=Pascal Boyer|titre=Petit compagnon des nombres et de leurs applications|lieu=Paris|éditeur=Calvage et Mounet|année=2019|pages totales=648|passage=17-19|isbn=978-2-916352-75-6|partie=|numéro chapitre=2.1.|titre chapitre=Jouer à la marchande}}.</ref> :

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

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

Ce théorème fait partie de ceux du [[folklore mathématique]] dont on ne connaît pas le découvreur<ref name="BR16" />. Il est extrêmement souvent<ref name="BR16" />{{,}}<ref name="Skup" /> attribué par erreur à [[James Joseph Sylvester]] en 1884<ref name="Sylv" />, alors qu'il le considérait sans doute comme connu<ref name="BR16" /> et que sa publication consistait en un autre exercice<ref>Cas particulier d'un théorème de {{Article|auteur=J. J. Sylvester|titre=Théorie des nombres|url=http://visualiseur.bnf.fr/CadresFenetre?O=NUMM-3007|page=367|année=1860|revue=[[Comptes rendus hebdomadaires des séances de l'Académie des sciences]]|vol=50|numéro=1}} cité dans {{Dickson1}}, [https://books.google.fr/books?id=dO7C02z4LlcC&pg=PA66 vol. II, chap. 2, {{p.|66}}].</ref>, que l'on peut dès lors reformuler<ref>Pour une formulation plus fidèle à {{Harvsp|Sylvester|1884}} et une démonstration différente, voir « [[Équation diophantienne ax + by = c#Recherche de solutions dans l'ensemble des entiers naturels|Théorème de Cesàro]] » dans l'article détaillé.</ref> ainsi : démontrer que
{{Retrait|parmi les entiers de 0 à <math> g(a,b) </math><ref name=BR6/>, exactement la moitié sont représentables.}}Cette propriété se déduit du lemme précédent car si <math>A_1</math> est l'ensemble des nombres de 0 à <math>g(a,b)</math> qui sont représentables, et <math>A_2</math> celui de ceux qui ne le sont pas, l'application <math>m\mapsto g(a,b)-m</math> définit une bijection de <math>A_1</math> sur <math>A_2</math>.

=== ''n'' = 3 ===
On connaît des algorithmes rapides pour le calcul du nombre de Frobenius de trois entiers <math>a_1, a_2, a_3</math> (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 [[minorant]]s et des [[majorant]]s pour les nombres de Frobenius de trois entiers. Des données expérimentales<ref name=BZ/> montrent que la minoration de Davison<ref name=Dav/>,
:<math>g(a_1, a_2, a_3) \geqslant \sqrt{3a_1a_2a_3} - a_1 - a_2 - a_3,</math>
est assez fine.

Dans le cas où <math>a_1=ab, a_2=bc, a_3=ca</math> où <math>a,b,c</math> sont trois entiers strictement positifs premiers entre eux deux à deux, le nombre de Frobenius est connu<ref>Problème 3 des [[olympiades internationales de mathématiques]] 1983</ref>{{,}}<ref name="boyer" /> :
:<math>g(ab,bc,ca) =2abc-ab-bc-ca</math>.
== Nombres de Frobenius pour des ensembles particuliers ==
La formule ci-dessus pour <math>n=2</math> se généralise de deux façons.

=== Cas d'entiers premiers deux à deux ===
Si <math>a_1,a_2,\cdots,a_n</math> sont des entiers strictement positifs deux à deux premiers entre eux, alors<ref name="boyer" />

:<math>g\left(\frac\pi{a_1},\frac\pi{a_2},\dots,\frac\pi{a_n}\right) =\pi\left(n-1-\sum_{i=1}^n\frac1{a_i}\right)</math> où <math>\pi=a_1\cdots a_n</math>.

=== Suites arithmétiques ===
Un formule simple existe pour des entiers en [[suite arithmétique|progression arithmétique]]<ref name=ramirez59/>. Étant donné trois entiers strictement positifs  <math>a, d, s</math>, avec <math>\operatorname{pgcd}(a,d)=1</math>, on a :

: <math>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.</math>
Par exemple, les suites <math>(g(n,n+1,\dots,n+k))_n</math> pour <math>k=2,\dots,8</math> sont répertoriées dans l'[[OEIS]] : {{OEIS2C|A028387}} , {{OEIS2C|A079326}}, {{OEIS2C|A138984}}, {{OEIS2C|A138985}}, {{OEIS2C|A138986}}, {{OEIS2C|A138987}}, {{OEIS2C|A138988}}.

=== Suites géométriques ===
De même, il existe une formule explicite pour un cas particulier d'entiers en
[[suite géométrique|progression géométrique]]<ref name= Ong/>. Étant donné trois entiers strictement positifs <math>m, n, k</math>, avec <math>\operatorname{pgcd}(m,n)=1</math>, on a :

: <math>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}.</math>

== Exemples élémentaires ==
=== Nombres {{Lang|en|McNugget}} ===
[[Image:Chicken McNuggets.jpg|vignette|''{{Lang|en|[[McDonald's]] [[Chicken McNuggets]]}}'' dans une boîte de 20.]]
[[Fichier:Chicken McNuggets Problem - graphical representation.jpg|vignette|Solution graphique au problème des ''{{Lang|en|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 {{Lang|en|McNugget}}'''<ref name=McN/>{{,}}<ref name=MW/> est un cas particulier du problème des pièces de monnaie.

Un [[nombre]] <math>n</math> est dit {{Lang|en|McNugget}} si l'on peut, en choisissant bien ses boîtes de ''{{Lang|en|[[Chicken McNuggets]]}}'', parvenir à un total de <math>n</math> {{Lang|en|[[Croquette de poulet|nuggets]]}}. Les boîtes classiques contiennent [[6 (nombre)|6]], [[9 (nombre)|9]] ou [[20 (nombre)|20]] {{Lang|en|nuggets}}. D'après [[Théorème de Schur#En combinatoire|un théorème de Schur]], comme 6, 9 et 20 sont [[Nombres premiers entre eux#Extension à n nombres|premiers entre eux dans leur ensemble]], tout [[Entier relatif|entier]] « assez grand » peut être exprimé comme [[combinaison linéaire]] à coefficients [[Entier naturel|entiers positifs]] de ces trois nombres. Autrement dit : il existe un plus grand nombre qui n'est pas un nombre {{Lang|en|McNugget}} — c'est le nombre de [[Ferdinand Georg Frobenius|Frobenius]] de l'[[ensemble]] {6, 9, 20}.

Mais on peut expliciter complètement cet [[Exemple (mathématiques)|exemple]], sans invoquer le théorème de Schur, en [[démonstration (logique et mathématique)|démontrant]] directement que le plus grand entier qui n'est pas un nombre {{Lang|en|McNugget}} est [[43 (nombre)|43]] :
* tous les entiers à partir de 44 sont des nombres {{Lang|en|McNugget}} car
:{| class="wikitable"
|-
| [[44 (nombre)|44]] = 6 + 9 + 9 + 20&nbsp;
| [[45 (nombre)|45]] = 9 + 9 + 9 + 9 + 9&nbsp;
| [[46 (nombre)|46]] = 6 + 20 + 20&nbsp;
|-
| [[47 (nombre)|47]] = 9 + 9 + 9 + 20&nbsp;
| [[48 (nombre)|48]] = 6 + 6 + 9 + 9 + 9 + 9&nbsp;
| [[49 (nombre)|49]] = 9 + 20 + 20&nbsp;
|}
:et tout entier plus grand [[Congruence sur les entiers|s'obtient en additionnant un certain nombre de 6]] à l'une de ces [[Partition d'un entier|partitions]] ;
* 43 n'est pas un nombre {{Lang|en|McNugget}}<ref name=Clip/> : on ne peut pas obtenir 43 {{Lang|en|nuggets}} avec seulement des boîtes de 6 et 9 car le résultat est un [[Critère de divisibilité#Par 3|multiple de 3]]. Si l'on prend une seule boîte de 20, on ne peut pas faire mieux parce que les [[23 (nombre)|23]] {{Lang|en|nuggets}} restants ne forment pas un [[Multiple (mathématiques)|multiple]] de [[3 (nombre)|3]]. Enfin, en prenant deux boîtes de 20, il reste 3 {{Lang|en|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 {{Lang|en|McNugget}} (leur liste est la {{OEIS|id=A065003}} : 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 [[Zéro|0]], égal à la [[somme vide]]).

;Variantes
* Depuis l'introduction d'une boîte ''{{Lang|en|[[Happy Meal]]}}'' de 4 {{Lang|en|nuggets}}, le plus grand nombre qui n'est pas {{Lang|en|McNugget}} descend à [[11 (nombre)|11]].
* Dans certains pays où la boîte de 9 {{Lang|en|nuggets}} est remplacée par une boîte de [[10 (nombre)|10]], on ne peut obtenir qu'un [[nombre pair]] de {{Lang|en|nuggets}}, si bien qu'aucun [[nombre impair]] n'est un nombre {{Lang|en|McNugget}}.
{{clr}}

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

== Notes et références ==
{{Traduction/Référence|en|Coin Problem|552004016|type=note}}
{{Références|colonnes=2|références=
<ref name=Clip>{{en}} [[Brady Haran]], [https://www.youtube.com/watch?v=vNTSugyS038 How to order 43 Chicken McNuggets - Numberphile] « Comment commander 43 [[Nugget de poulet|croquettes de poulet]] ».</ref>
<ref name=BraSho>{{Article|lang=en|titre=On a problem of Frobenius|auteur2=James E. Shockley|auteur=Alfred Brauer|revue=[[Journal für die reine und angewandte Mathematik|J. Reine Angew. Math.]]|vol=211|année=1962|p.=215-220|url=http://www.digizeitschriften.de/dms/img/?PPN=PPN243919689_0211&DMDID=dmdlog24}}.</ref>
<ref name=MW>{{MathWorld | nom_url=McNuggetNumber | titre=McNugget Number}}.</ref>
<ref name=Dav>{{Article|lang=en|titre=On the Linear Diophantine Problem of Frobenius|auteur=J. L. Davison|revue=Journal of Number Theory|vol=48|numéro=3|année=1994|p.=353-363|doi=10.1006/jnth.1994.1071}}.</ref>
<ref name=Bra>{{Article|lang=en|titre=On a Problem of Partitions|auteur=[[Alfred Brauer]]|revue=[[American Journal of Mathematics|Amer. J. Math.]]|vol=64|numéro=1|année=1942|p.=299-312|jstor=2371684}}.</ref>
<ref name=BR16>{{Ouvrage|langue=en|auteur1=Matthias Beck|auteur2=Sinai Robins|titre=Computing the Continuous Discretely|sous-titre=Integer-point Enumeration in Polyhedra|éditeur=Springer|année=2007|passage=16|lire en ligne=https://www.springer.com/cda/content/document/cda_downloaddocument/9780387291390-c1.pdf|numéro chapitre=1|titre chapitre=The Coin-Exchange Problem of Frobenius}}.</ref>
<ref name=BR6>Ou encore : de 1 à (''a'' – 1)(''b'' – 1), {{cf.}} {{Harvsp|Beck|Robins|2007|p=6}}.</ref>
<ref name=ramirez>{{Ouvrage|langue=en|prénom1=Jorge L.|nom1=Ramírez Alfonsín|titre=The Diophantine Frobenius problem|éditeur=[[Oxford University Press|Oxford Univ. Press]]|collection=Oxford Lecture Series in Mathematics and its Applications|numéro dans collection=30|année=2005}}.</ref>
<ref name=kannan>{{article|lang=en|auteur=[[Ravi Kannan]]|année=1992 |titre=Lattice translates of a polytope and the Frobenius problem |journal=Combinatorica |volume=12 |numéro=2 |pages=161-177 |doi=10.1007/BF01204720}}.</ref>
<ref name=FF>{{article|lang=en|prénom1=D. |nom1=Beihoffer|prénom2=J. |nom2=Hendry|auteur3={{Lien|Albert Nijenhuis|texte=A. Nijenhuis}}|auteur4=[[Stan Wagon|S. Wagon]]|titre=Faster algorithms for Frobenius numbers |journal=Electronic Journal of Combinatorics |année=2005 |volume=12 |pages=R27 |url=http://www.combinatorics.org/Volume_12/Abstracts/v12i1r27.html}}.</ref>
<ref name=mw>{{MathWorld|nom_url=CoinProblem|titre=Coin Problem}}.</ref>
<ref name=Sylv>{{article|lang=en|prénom1 =J. J.|nom1= Sylvester | année = 1884| titre =[Question] 7382 (Solution by W. J. Curran Sharp)|journal = Mathematical Questions from the Educational Times| volume = 41| page=21 |url=https://archive.org/stream/mathematicalque05unkngoog#page/n150}}.</ref>
<ref name=Skup>{{article|lang=en|auteur={{Lien|Zdzisław Skupień}}|titre=A generalization of Sylvester's and Frobenius' problems|journal=[[Liste des journaux scientifiques en mathématiques#A|Acta Arithmetica]]|année=1993|volume=65|numéro=4|pages=353-366|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa65/aa6545.pdf}}.</ref>
<ref name=BZ>{{article|lang=en|prénom1=M. |nom1=Beck|prénom2=S. |nom2=Zacks |titre=Refined upper bounds for the linear Diophantine problem of Frobenius |journal=Adv. Appl. Math. |volume=32 |année=2004 |pages=454-467 |doi=10.1016/S0196-8858(03)00055-1 |arxiv=math/0305420 |numéro=3}}.</ref>
<ref name=ramirez59>{{harvsp|Ramírez Alfonsín|2005|p=59-69}}.</ref>
<ref name=Ong>{{article|lang=en| nom1= Ong|prénom1= Darren C. |nom2= Ponomarenko|prénom2= Vadim | année = 2008| titre = The Frobenius Number of Geometric Sequences| journal = INTEGERS: the Electronic Journal of Combinatorial Number Theory |volume = 8 |titre volume = A33 |url=http://www.emis.ams.org/journals/INTEGERS/vol8.html }}.</ref>
<ref name=McN>{{Ouvrage|langue=en|prénom1=Anita|nom1=Wah|prénom2=Henri|nom2=Picciotto|titre=Algebra|sous-titre=Themes, Tools, Concepts|année=1994|passage=186|lire en ligne=http://www.mathedpage.org/attc/lessons/ch.05/5.08-building-blocks.pdf|titre chapitre=Lesson 5.8 Building-block Numbers}}.</ref>
}}

== Voir aussi ==
=== Articles connexes ===
* {{Lien|langue=en|trad=Postage stamp problem|fr=Problème des timbres-poste}}
* {{Lien|langue=en|fr=Sylver coinage}}

=== Lien externe ===
{{Lien web|url=http://images.math.cnrs.fr/Pieces-et-billets.html|titre=Pièces et billets|auteur=[[Jean-Paul Allouche]]|site=[[images des Maths]]|date=9/10/2009}}

{{Portail|mathématiques}}

[[Catégorie:Théorie des nombres]]
[[Catégorie:Mathématiques récréatives]]