Enoncé :
On dispose de billets de 5€ et de billets de 20€.
De combien de façons peut-on obtenir la somme de 165€ ?
Solution :
Cela revient à résoudre l’équation diophantienne 5x+20y = 165d’inconnues x et y (entiers naturels).
On peut diviser par 5 chaque membre de l’équation sans changer la nature des solutions (car \mathrm{PGCD}(5,20) = 5 et 165 est un multiple de 5), on obtient alors :
5x+20y = 165 \iff x + 4y = 33.
On donne la solution particulière de x + 4y = 1 :
4 = 3 + 1 \iff 1 = 4 - 3Ainsi la solution particulière de x + 4y = 1 est le couple (-3;1). On en déduit alors la solution particulière de x + 4y = 33 qui est le couple (-99;33).
Pour déterminer la solution générale de l’équation diophantienne x + 4y = 33, on peut combiner les deux égalités : x+4y = 33 et -99 + 4 \times 33 = 33. On obtient ainsi (en faisant la différence des deux) :
(x+99) + 4(y-33) = 0 \iff (x+99) = - 4(y-33)Ici -4 divise x+99 donc il existe k entier relatif tel que x+99 = -4k \iff x = -4k-99. Avec un même raisonnement, on peut conclure que y = k + 33.
Mais il faut que les entiers x et y soient positifs, donc il faut ajouter une nouvelle condition :
\begin{cases} x \ge 0 \\ y \ge 0\end{cases} \iff \begin{cases} -4k-99 \ge 0 \\ k+33 \ge 0\end{cases} \iff \begin{cases} -4k \ge 99 \\ k \ge -33\end{cases} \iff \begin{cases} k \le -\dfrac{99}{4} \\ k \ge -33\end{cases}Ainsi, on trouve un encadrement qui convient pour répondre à la question de l’énoncé :
-33 \le k \le -25On peut lister ainsi les 9 façons d’obtenir la somme de 165€ avec des billets de 5€ et des billets de 20€.
| k | x | y | 5x+20y |
| -33 | 33 | 0 | 165 |
| -32 | 29 | 1 | 165 |
| -31 | 25 | 2 | 165 |
| -30 | 21 | 3 | 165 |
| -29 | 17 | 4 | 165 |
| -28 | 13 | 5 | 165 |
| -27 | 9 | 6 | 165 |
| -26 | 5 | 7 | 165 |
| -25 | 1 | 8 | 165 |
Références :
- L’énoncé sur le site du jury (page 5)
- Les solutions de G. Julia