Exercice 3 — Le pays aux pièces 1-3-9-27-81

Sujet

Dans un pays ne circulent que des pièces de 1, 3, 9, 27 et 81 euros, tous les prix étant des entiers. Un paiement est un achat réglé exactement (sans rendu). Une transaction est un achat réglé avec un rendu éventuel de monnaie.

De combien de façons différentes peut-on effectuer un paiement de 21 € ?
Donner une façon de payer 183 €. Laquelle utilise le moins de pièces ?
Montrer que tout paiement peut s'effectuer avec des pièces de 81 € et, au plus, deux pièces de chacune des autres valeurs.
On dit qu'une personne possède un jeu si elle a exactement une pièce de chaque valeur. a) Quels paiements une personne avec un jeu peut-elle effectuer ? Peut-elle payer 11 € ? b) Deux personnes avec chacune un jeu peuvent-elles réaliser une transaction de 11 € ? c) Quel est le montant maximal d'une transaction entre elles ? Montrer que toute transaction inférieure est réalisable.

Remarquer que \(3=3\times1\), \(9=3\times3\), \(27=3\times9\), \(81=3\times27\) : chaque valeur vaut 3 fois la précédente. Pour minimiser le nombre de pièces (question 2-3), utiliser une suite de divisions euclidiennes en cascade, en commençant par la plus grande valeur (81), un peu comme une écriture en base 3. Pour la question 4c, penser à ce que peut faire un « rendu de monnaie » : remplacer 3 pièces d'une valeur par 1 pièce de la valeur supérieure, ou l'inverse, en jouant sur qui donne et qui rend.

1. En listant toutes les combinaisons de pièces de 1, 3 et 9 € (21 € étant inférieur à 27) sommant à 21 : il y a 15 façons différentes (de \(21\times1€\) à \(1\times9+4\times3+0\times1\), etc.).

2. \(183=2\times81+21\), puis \(21=2\times9+3\). Paiement minimal : 2 pièces de 81 €, 2 pièces de 9 €, 1 pièce de 3 € (5 pièces au total).

3. Par une cascade de divisions euclidiennes : \(n=81q_1+r_1\) (\(0\leqslant r_1<81\)), puis \(r_1=27q_2+r_2\) (\(0\leqslant r_2<27\), donc \(q_2\in\{0,1,2\}\) car \(r_1<81=3\times27\)), puis de même pour 9, puis 3, puis le reste final \(r_4\in\{0,1,2\}\) réglé en pièces de 1 €. À chaque étape, le quotient (nombre de pièces de cette valeur) est nécessairement 0, 1 ou 2 — ce qui prouve le résultat pour toute somme \(n\).

4a. Avec 5 pièces (1,3,9,27,81), chaque pièce est utilisée ou non dans un paiement : \(2^5=32\) possibilités, moins le cas « aucune pièce » : 31 prix différents payables. Comme \(11=9+1+1\) n'est pas réalisable avec une seule pièce de chaque (on n'a qu'un seul 1 €), il faut vérifier : avec un jeu {1,3,9,27,81}, les sommes possibles sont tous les sous-ensembles non vides — \(11\) ne s'obtient pas exactement (le plus proche est \(9+3=12\) ou \(9+1=10\)) : non, on ne peut pas payer exactement 11 € avec un seul jeu.

4b. Mais avec un rendu de monnaie entre les deux jeux : l'acheteur donne \(3+9=12\) €, le vendeur lui rend \(1\) € : la transaction de 11 € est bien réalisable.

4c. Le montant maximal qu'un acheteur peut fournir avec son jeu complet est \(1+3+9+27+81=121\) €. C'est le montant maximal d'une transaction. Pour tout montant \(n<121\) : on part d'une décomposition à au plus 2 pièces de chaque valeur (question 3), puis on ajuste de proche en proche (des plus petites aux plus grandes valeurs) : dès qu'il faudrait 2 pièces d'une valeur alors qu'on n'en a qu'une, on utilise 1 pièce de la valeur supérieure et le vendeur rend la différence — un processus qui se termine toujours car chaque ajustement ne peut se propager qu'un nombre fini de fois (jusqu'à 81 €, la plus haute valeur).

Exemple donné dans le corrigé, pour 95 € : \(95=81+9+3+2\times1\) (nécessite 2 pièces de 1€, indisponible) \(\to95=81+9+3\times2-1\) (2 pièces de 3€, indisponible) \(\to95=81+2\times9-3-1\) (2 pièces de 9€, indisponible) \(\to95=81+27-9-3-1\) : l'acheteur donne 81+27=108 €, le vendeur rend 9+3+1=13 € — vérification : \(108-13=95\) ✓.

Exercice 3 — Le pays aux pièces 1, 3, 9, 27, 81

Sujet