Autour du rendu de monnaie

Cette séance s’articule autour du problème général du rendu de monnaie, qui consiste à déterminer de quelle façon obtenir une somme donnée en utilisant des pièces qui ne peuvent prendre que certaines valeurs imposées. Par exemple, « comment obtenir une somme de 28€43 avec des pièces de 1€ et 2€ et des pièces de 1, 2, 5, 10, 20 et 50 centimes ». C’est le problème que doit résoudre un commerçant lorsqu’il rend la monnaie, d’où le nom du problème.

On spécifie un peu plus la question telle qu’elle sera étudiée dans la suite :

• on considère qu’il n’y a pas de contraintes a priori sur le nombre de pièces disponibles de chaque espèce (donc « 2843 pièces de 1 centime » est une solution recevable à la question donnée en exemple);

• on cherche à déterminer des décompositions dites optimales, c’est-à-dire qui utilisent le moins de pièces possible (la décomposition « 2843 pièces de 1 centime » n’est pas optimale, on peut faire mieux).

Première approche

1. Donner une décomposition optimale de 28€43 en utilisant les pièces et billets usuels de l’euro. Justifier que la réponse est optimale.

Dans l’ancien système monétaire britannique qui avait cours avant 1971, la livre sterling était divisée en 20 shillings divisés chacun en 12 pence (pluriel de penny). La valeur des différentes pièces existantes était 1, 3, 4, 6, 12, 24, 30, 60, 120, 240 et 252 pence. Depuis 1971, c’est un système décimal qui est utilisé avec les mêmes valeurs que dans le système de l’euro.

2. Donner une décomposition optimale de la somme de 49 pence dans l’ancien système britannique. Justifier la réponse.

Formalisation

Fixons les notations :

• On représente par une liste S = (s₁,s₂,…,s_n) le système de pièces, avec les valeurs entières rangées en ordre strictement croissant (on ramène toutes les pièces à des multiples d’une même unité).

• On représente une décomposition par une liste D = (d₁,d₂,…,d_n) d’entiers naturels, où d_i est le nombre d’exemplaires de la pièce de valeur s_i.

• On notera v la valeur à décomposer.

Le problème est donc, étant donnés S et v, de trouver un D

• tel que $\sum_{i=1}^n d_i s_i=v$ (c’est une décomposition de v)
• qui minimise $\sum_{i=1}^n d_i$ (elle est optimale).

Avant de chercher une décomposition optimale, il faut déjà savoir s’il y a au moins une décomposition. Si c’est le cas, alors il y en a forcément au moins une qui est optimale, éventuellement plusieurs.

3. Donner une condition nécessaire et suffisante sur le système S pour que tout entier v ait au moins une décomposition D.

Algorithme glouton

L’algorithme dit glouton est celui qui consiste à décomposer la somme en privilégiant systématiquement la pièce la plus grande possible pour la somme restant à décomposer.

4. Écrire proprement l’algorithme glouton pour le rendu de monnaie.

5. Démontrer que l’algorithme termine toujours, en supposant que la condition de la question 3 est satisfaite.

6. Démontrer que ce qu’il renvoie est bien une décomposition. On ne cherche pas à savoir pour le moment si cette décomposition est optimale.

Systèmes canoniques

Un système S est dit canonique si l’algorithme glouton donne toujours une décomposition optimale.

7. Montrer que l’ancien système britannique n’est pas canonique.

8. Montrer qu’un système de la forme (1,2,4,8,16,…,2^m) est canonique.

9. Montrer que le système de l’euro (1,2,5,10,20,50,100,200) est canonique.

10. Plus généralement, déterminer une condition suffisante pour qu’un système soit canonique.

Solution générale

Pour aller plus loin, élaborer un algorithme qui donne une décomposition optimale même dans le cas d’un système qui n’est pas canonique. Estimer le nombre d’étapes nécessaire dans le pire des cas pour résoudre une instance du problème avec cet algorithme.