Le problème des pièces de monnaie
Comment payer avec seulement 2 ou 3 billets ?
En Mathématiques il existe des énoncés simples, mais qui mettent à mal l’ensemble de la communauté des Mathématiciens ! Je vais ici vous en présenter un !
1. Une monnaie particulière
Imaginez un monde fictif, dans lequel il n’existe que 2 billets différents pour payer : des billets de 2, et des billets de 5. Ici, pas de centimes !
Dans ce pays toutes les sommes d’argent ne sont pas payables (j’entends par là sans rendu de monnaie) ! En effet, il ne serait pas possible de faire un appoint de 3 ou de 7 ! Demandons-nous quelles sommes d’argent il est possible de payer. Je vais lister en vert les sommes possibles, et en rouge celles impossibles à atteindre :
On obtient par exemple 11 avec un billet de 5 et 3 billets de 2. Cet exemple nous laisse entendre qu’à partir de 4, toutes les sommes sont payables. Et c’est le cas !
C’est assez facile de s’en rendre compte. Déjà, toutes les sommes paires le sont (avec uniquement des billets de 2). Pour les nombres impairs à partir de 5, il suffit de prendre un billet de 5 et de compléter avec des billets de 2.
Très bien ! Mais que se passerait-il avec 2 billets de valeur différente ?
2. Un problème à 2 balles
Il s’agit en fait d’un célèbre problème dit « problème des pièces de monnaie (ou billets) ».
Prenons 2 nombres entiers a et b (nos valeurs de billets). On se demande s’il existe un seuil à partir duquel toutes les sommes seront payables. Ce problème se traduit mathématiquement avec des combinaisons linéaires à coefficients entiers positifs. Les sommes payables sont celles de la forme :
avec m1 et m2 deux nombres entiers positifs premiers entre eux*.
On parle de problème diophantien (le monde des équations polynomiales étudiées sur les nombres entiers).
Petite note * : pour préciser, il faut que nos 2 nombres a et b soient premiers entre eux, autrement dit que leur seul diviseur positif en commun soit 1. En effet, si l’on prend par exemple des billets de 2 et de 6 (ici les 2 nombres sont divisibles par 2), il est clair que chaque somme impaire sera impayable !
Aujourd’hui, on sait que pour 2 billets, de valeurs premières entre elles, il existera toujours un seuil à partir duquel toutes sommes seront payables ! On appelle nombre de Frobenius (Ferdinand Georg Frobenius, Mathématicien Allemand) la plus grande somme non payable ! Et même mieux, on sait déterminer sa valeur qui est : ab – a – b.
Par exemple, avec les billets 2 et 5 on obtient bien 2 × 5 - 2 - 5 = 3 !
Prenons un autre exemple ! Imaginez-vous devant un stand de churros. Ceux-ci sont vendus par paquets de 7 ou de 12 (et ça c’est génial : 2 nombres premiers entre eux !). Quelle est la plus grande quantité de churros que l’on ne peut pas acheter ?
On calcule 12 × 7 – 12 – 7 = 65. A partir de 66 churros (2 paquets de 12 et 6 paquets de 7), toutes les quantités seront achetables (ce qui fait un gros goûter) ! Avant ça, il faut regarder au cas par cas !
3. Et pour le problème à 3 balles, ou plus ?
On peut légitimement se demander ce qu’il se passe si l’on ajoute un 3ème billet à notre monnaie ! Je passe les détails, mais en pratique il faut que les 3 sommes soient premières entre elles dans leur ensemble (passons).
Illustrons le problème avec une situation connue : celle du rugby. Dans ce sport, les points s’obtiennent par 3 (pénalité), 5 (essai non transformé) ou 7 (essai transformé). On peut se demander quels sont les scores possibles !
Il est facile de voir que 1, 2 et 4 sont impossibles. Notons qu’il est simple d’obtenir 5, 6 ou 7. A partir de là, on peut en ajoutant k drops obtenir les nombres 5 + k, 6 + k et 7 + k, ce qui correspond à l’ensemble des entiers à partir de 5. Les seuls scores impossibles sont donc 1, 2 et 4. Ici, le nombre de Frobenius est donc 4 !
Dans le cas général, pour 3 billets et plus, le problème se corse considérablement ! On connait des méthodes de calcul du nombre de Frobenius, mais qui sont parfois très complexes à mettre en œuvre.
L’existence du nombre de Frobenius est déja un poil technique à mettre en évidence (on utilise notamment le théorème de Schur, celui sur la combinatoire. Magnifique, mais pas si simple d’accès !).
Pour ne pas m’avancer sur un terrain que je ne maitrise plus, je vais donc m’arrêter là. Comme vous le voyez, en Mathématiques, une question d’apparence simple et amusante, peut se transformer en véritable casse-tête !