3.3 Problème de pièces de monnaie

Nous allons maintenant nous intéresser au problème des pièces de monnaie de Frobenius. Au Royaume-Uni, les pièces de monnaie ont les dénominations $\displaystyle 1$ penny, $\displaystyle 2$ pence, $\displaystyle 5$ pence, $\displaystyle 10$ pence, $\displaystyle 20$ pence, $\displaystyle 50$ pence, $\displaystyle 1$ pound et $\displaystyle 2$ pounds. En utilisant seulement des pièces de $\displaystyle 2$ pence et $\displaystyle 5$ pence, quel est le plus grand montant d’argent qu’il est impossible de faire ?

Par essaie et erreur, on peut facilement construire le tableau suivant:

Montant	Représentation
1	impossible
2	2
3	impossible
4	2 + 2
5	5
6	2 + 2 + 2
7	5 + 2
8	2 + 2 + 2 + 2
9	5 + 2 + 2
10	2+2+2+2+2 ou 5+5

Nous allons maintenant utiliser le principe d’induction généralisé pour montrer qu’il est possible de réaliser tous les entiers supérieurs ou égaux à $\displaystyle 4$ (donc $\displaystyle 3$ est le plus grand montant qu’il est impossible de faire). Nous savons déjà qu’il est possible de faire $\displaystyle 4$ et $\displaystyle 5$ . Supposons qu’il soit possible de réaliser tous les montants d’argent entre $\displaystyle 4$ et $\displaystyle k$ avec $\displaystyle k\geq 6$ . On veut maintenant montrer qu’il est possible de faire $\displaystyle k+1$ . Pour ce faire, il suffit de remarquer que, par hypothèse, il est possible de faire $\displaystyle k-1$ , et qu’en ajoutant une pièce de 2 pence, on obtient $\displaystyle k+1$ . Il est donc possible de réaliser $\displaystyle k+1$ . Par le principe d’induction généralisé, il est donc possible de faire tous les montants d’argent supérieurs ou égaux à $\displaystyle 4$ pence.

Bien que nous sachions qu’il soit possible de réaliser tous les montants $\displaystyle\geq 4$ , une autre question liée est de savoir de combien de façons cela peut être réalisé. Nous avons déjà remarqué qu’un montant de $\displaystyle 10$ pence peut être réalisé de (au moins) deux façons différentes, mais pour les autres, nous ne savons pas encore. Pour ce faire, nous allons considérer deux approches différentes. La première en utilisant les récurrences, et la seconde en utilisant les fonctions génératrices. Pour conclure cette section, nous allons faire quelques commentaires concernant les différences importantes entre les deux méthodes.

Solution à l’aide d’une récurrence

Dans un premier temps, remarquons qu’il est impossible de faire un montant de $\displaystyle 1$ penny et de $\displaystyle 3$ pence. De plus, il existe exactement une façon de faire un montant de $\displaystyle 2$ , $\displaystyle 4$ et $\displaystyle 5$ pence. Ces valeurs nous serviront de valeurs initiales pour notre problème. Maintenant, remarquons que pour faire un montant de $\displaystyle n$ pence, on peut prendre un montant de $\displaystyle n-2$ pence et ajouter une pièce de $\displaystyle 2$ pence, ou prendre un montant de $\displaystyle n-5$ pence et ajouter une pièce de $\displaystyle 5$ pence. On obtient donc la récurrence suivante:

\displaystyle\left\{\begin{array}[]{l}a_{1}=0\\ a_{2}=1\\ a_{3}=0\\ a_{4}=1\\ a_{5}=1\\ a_{n}=a_{n-2}+a_{n-5},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \forall n\geq 6\end{array}\right.

À partir de cette récurrence, il nous est maintenant facile de compléter le tableau ci-dessous.

$\displaystyle n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\displaystyle a_{n}$	0	1	0	1	1	1	2	1	3	2	4	4	5	7	7

Ce qui a été accompli à l’aide du code Python suivant:

Listing 20: Pièces de monnaie: Récurrence

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              def a(n):


                6
                
                
                
                  if n == 1:


                7
                
                
                
                      return 0


                8
                
                
                
                  if n == 2:


                9
                
                
                
                      return 1


                10
                
                
                
                  if n == 3:


                11
                
                
                
                      return 0


                12
                
                
                
                  if n == 4:


                13
                
                
                
                      return 1


                14
                
                
                
                  if n == 5:


                15
                
                
                
                      return 1


                16
                
                
                
                  else:


                17
                
                
                
                      return a(n-2) + a(n-5)


                18
                
                
                
              


                19
                
                
                
              tableau = DataFrame([[a(n) for n in range(1,16)]])


                20
                
                
                
              tableau.columns = [n for n in range(1,16)]


                21
                
                
                
              tableau.index = ["Valeurs"]


                22
                
                
                
              tableau

Solution à l’aide des fonctions génératrices ordinaires

Pour résoudre le problème avec les fonctions génératrices, nous allons commencer par trouver une fonction génératrice correspondant aux pièces de $\displaystyle 2$ pence, puis aux pièces de $\displaystyle 5$ pence séparément, et enfin combiner les deux séries génératrices pour obtenir notre solution.

En utilisant uniquement les pièces de $\displaystyle 2$ pence, il n’existe aucune façon de faire un montant impair et exactement une façon de faire un montant pair. Cela nous donne donc la fonction génératrice suivante:

\displaystyle 1+0x^{1}+1x^{2}+0x^{3}+1x^{4}+0x^{5}+1x^{6}+0x^{7}+...=1+x^{2}+x% ^{4}+x^{6}+x^{8}+...=\sum_{k=0}^{\infty}x^{2k}=\sum_{k=0}^{\infty}(x^{2})^{k}=% \frac{1}{1-x^{2}}

Pour les pièces de $\displaystyle 5$ pence, l’idée est semblable. Il existe exactement une façon de faire tous les multiples de $\displaystyle 5$ , et aucune pour les autres valeurs. La fonction génératrice est donc:

\displaystyle 1+x^{5}+x^{10}+x^{15}+x^{20}+...=\sum_{k=0}^{\infty}x^{5k}=\sum_% {k=0}^{\infty}(x^{5})^{k}=\frac{1}{1-x^{5}}

Maintenant, pour obtenir le nombre de façons de faire un montant de $\displaystyle n$ pence en utilisant des pièces de $\displaystyle 2$ pence et de $\displaystyle 5$ pence, il nous suffit tout simplement de multiplier les deux fonctions génératrices et de prendre les coefficients de la série. La fonction génératrice décrivant le problème est donc:

\displaystyle\sum_{n=0}^{\infty}a_{n}x^{n}=\frac{1}{(1-x^{2})(1-x^{5})}

Nous n’avons cependant aucune façon, du moins pour le moment, de réécrire cette fonction sous forme de série. L’idée de prendre les coefficients n’est donc pas possible pour le moment sans l’utilisation de logiciel. En se limitant à un montant de $\displaystyle 15$ pence comme nous l’avons fait avec les récurrences, il nous est cependant possible de résoudre le problème en effectuant uniquement la multiplication de deux polynômes. On a donc:

\displaystyle(1+x^{2}+x^{4}+x^{6}+x^{8}+x^{10}+x^{12}+x^{14})(1+x^{5}+x^{10}+x% ^{15})=

\displaystyle 1+x^{2}+x^{4}+x^{5}+x^{6}+x^{7}+x^{8}+x^{9}+2x^{10}+x^{11}+2x^{1% 2}+x^{13}+2x^{14}+2x^{15}+...+x^{27}+x^{29}

Nous pouvons ignorer les termes de degré supérieur, car ils ne peuvent pas contribuer au coefficient de $\displaystyle x^{k}$ pour des valeurs de $\displaystyle k\leq 15$ . En prenant les coefficients, nous obtenons donc le tableau suivant:

$\displaystyle n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\displaystyle a_{n}$	0	1	0	1	1	1	1	1	1	2	1	2	1	2	2

Le même tableau peut être obtenu en utilisant directement la fonction génératrice et le code Python suivant:

Listing 21: Pièces de monnaie: Fonctions génératrices ordinaires

⬇


                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              x = Symbol(’x’)


                6
                
                
                
              fonction = 1 / ((1-x**2) * (1-x**5))


                7
                
                
                
              polynome = Poly(series(fonction, x, n=16).removeO()).all_coeffs()


                8
                
                
                
              polynome.reverse()


                9
                
                
                
              


                10
                
                
                
              tableau = DataFrame([polynome])


                11
                
                
                
              tableau.index = ["Valeurs"]


                12
                
                
                
              tableau

Comparaison des deux méthodes et conclusion partielle

En comparant les tableaux que nous avons obtenus pour chacune des deux méthodes, vous devriez remarquer un problème évident. Les valeurs ne sont pas identiques. Ceci n’a aucun sens, sauf si nous avons interprété le problème de deux façons différentes. c’est exactement ce qui s’est produit ici. Dans la méthode avec les récurrences, nous avons considéré que l’ordre était important. Un montant de $\displaystyle 7$ pence peut être obtenu en faisant $\displaystyle 2+5$ ou $\displaystyle 5+2$ . Il y a donc deux possibilités. Ceci se justifie en remarquant que notre récurrence nous affirme que pour faire $\displaystyle 7$ pence, on peut prendre un montant de $\displaystyle 2$ pence et ajouter $\displaystyle 5$ pence, ou prendre un montant de $\displaystyle 5$ pence et ajouter $\displaystyle 2$ pence.

Dans la méthode avec les fonctions génératrices, les choses sont un peu différentes. En effectuant le produit des deux polynômes, nous avons systématiquement pris les pièces de $\displaystyle 2$ pence en premier, puis les pièces de $\displaystyle 5$ pence. La conséquence est que nous avons indirectement supposé que l’ordre des pièces n’était pas important.

Conclusion: Les deux méthodes sont tout à fait correctes et permettent toutes les deux de résoudre le problème original. La différence était qu’une information importante manquait dans la question, et les deux méthodes nous ont permis de résoudre chacune une interprétation différente du problème.

Laquelle des deux solutions est la meilleure ? Cela dépend bien sur de l’interprétation du lecteur, mais en règle générale, nous considérerons la seconde interprétation comme plus intéressante. La raison est qu’en pratique, l’ordre des pièces que vous remettez au caissier est rarement important ; tout ce qui compte est d’avoir le bon montant. Il n’y a aucune raison que le caissier compte vos pièces exactement dans le même ordre que vous l’avez fait.