Pièces et billets

Le 9 octobre 2009  - Ecrit par  Jean-Paul Allouche Voir les commentaires (3)

Ecrire un premier billet, c’est un peu comme aller à un premier rendez-vous, le cœur battant. Le mot même de billet a un petit
côté délicieusement désuet. Qui écrit encore des billets doux à l’heure des SMS ? Qui comprend encore le sens de l’expression billet de confession, ou de l’image avoir une tête à coucher dehors avec un billet de logement ? ou encore de l’affirmation je vous fiche mon billet que...  ?
Même les contrôleurs dans les trains ne demandent plus si les billets sont poinçonnés mais si les titres de transport sont compostés — et ma question de vrai-faux ancien Parisien dans un bar-tabac de la rue Gay-Lussac il y a quelques années (« avez-vous des carnets de billets d’autobus ? ») ferait immédiatement croire au bistrotier qu’on tourne un film sur les années trente dans son quartier.

Mais on parle encore de billets de banque et de pièces de monnaie.
Nous sommes-nous déjà interrogés sur le choix des valeurs faciales
des pièces et des billets ? En euros, comme en francs, il y a des pièces
de 1, 2, 5, 10, 20 et 50 centimes, et des pièces de 1 et 2 francs (respectivement euros). Les billets de 5 et 10 euros n’avaient pas leurs
« pendants » en francs (au moins dans les quarante dernières années ou à peu près), ceux de 20, 50, 100, 200 et 500 euros
correspondent (pas en valeur, bien sûr) à leurs homologues en francs.

Ces valeurs faciales sont-elles universelles ? L’exemple des pièces aux USA et au Canada, montre que non : les valeurs sont en effet 1 et 5 cents
(penny et nickel), puis 10 et 25 cents (dime et quarter). On trouve parfois des demi-dollars ou des dollars aux USA, et il existe des pièces de un et de deux dollars au Canada (loonie et toonie). Nous avons tous été surpris un jour ou l’autre de voir le mécanisme de rendu de monnaie en Amérique du nord (même si le rituel « cinq, et dix qui nous font cent » est aussi devenu une rareté, même en France...).

Curieusement, dans un monde où dominent hélas le rendement, la rentabilité, l’efficacité, et plus généralement l’illusion que l’on peut et doit tout quantifier, personne n’a songé en haut lieu à
essayer d’optimiser (en l’occurrence de minimiser) le nombre moyen de pièces qu’on manipule lorsque l’on rend la monnaie. Il y a de jolies mathématiques derrière cette question : voici quelques indications extraites d’un article de J. Shallit qu’on lira avec intérêt et qui s’intitule What This Country Needs is a 18¢ Piece (paru dans
Math. Intelligencer 25 (2) (2003), 20-23 et disponible en version prétirage
ici, voir aussi les commentaires sur la
page de l’auteur).

J. Shallit fait l’hypothèse d’une répartition uniforme des prix entre
0¢ et 99¢ (ce qui, comme il l’indique, n’est pas tout à fait vrai, par exemple à cause de l’existence des prix psychologiques).
Pour chacune des valeurs de 0¢ à 99¢ on compte quel est le
nombre minimal de pièces pour atteindre cette valeur (par exemple, 30¢
peut s’obtenir comme 5+5+10+10, 10+10+10 ou 5+25 ; le nombre minimal de
pièces est 2). On fait ensuite la moyenne de tous ces nombres minimaux
pour toutes les valeurs comprises entre 0¢ et 99¢. Ce que J. Shallit
formalise ainsi.

Il se donne un ensemble de $D$ dénominations entières
$\{e_1 = 1 < e_2 < \cdots < e_D\}$ qui correspondent à des valeurs faciales de pièces et il veut représenter tout entier $N$ comme combinaison linéaire des $e_i$ à coefficients entiers positifs ou nuls
$N = \sum_{1 \leq i \leq D} a_i e_i$, où la somme
$S := \sum_{1 \leq i \leq D} a_i$ est minimale, disons égale à
opt$(N; e_1, e_2, \ldots, e_D)$. Il s’agit ensuite de minimiser la quantité
\[ \mbox{cost}(L, e_1, e_2, \ldots, e_D) := \frac{1}{L}\sum_{0 \leq N < L} \mbox{opt}(N; e_1, e_2, \ldots, e_D) \]
pour $L$ donné, par un choix judicieux des $e_i$.

Pour $L = 100$ et $D = 4$, autrement dit pour des prix entre 0¢ et 99¢ et quatre pièces différentes, le système américain
(1, 5, 10, 25) donne une moyenne de 4,7 pièces dans un rendu de monnaie.
L’optimum, une moyenne de 3,89 est obtenu avec des pièces de
(1, 5, 18, 25) ou (1, 5, 18, 29). Le choix du premier ensemble de pièces serait plus habile politiquement.

Pour en savoir plus sur cette question, on pourra lire l’article de J. Shallit cité plus haut, en particulier : le cas de l’euro, des questions algorithmiques (la plus simple étant le rapport avec l’algorithme glouton ou greedy algorithm de rendu de monnaie), le problème de Frobenius, le problème du timbre-poste ou postage stamp problem,
et des questions asymptotiques où intervient la moyenne de la somme des chiffres des entiers inférieurs à $N$. Rappelons juste pour allécher les lecteurs que cette moyenne a été étudiée par H. Delange en 1975, et qu’elle fait intervenir une fonction continue et nulle part dérivable. Quant à savoir si J. Shallit désirait « juste » faire des mathématiques jolies et inattendues ou s’il avait une
ambition politico-économique en écrivant son article (et si la réponse ne vous saute pas aux yeux), ne manquez pas de lire les commentaires sur sa
page.

Partager cet article

Pour citer cet article :

Jean-Paul Allouche — «Pièces et billets» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

  • Pièces et billets

    le 9 octobre 2009 à 22:21, par a.leblanc

    Très intéressant, mais il faut bien reconnaître que l’introduction d’une pièce de valeur 18 compliquerait les calculs, pour rendre la monnaie par exemple.

    Cela me rappelle mon premier programme : effectuer un programme de conversion pour la monnaie britannique quand une livre valait 20 shillings et 1 shilling 12 pences, mais c’est une autre histoire.

    Répondre à ce message
  • Pièces et billets

    le 8 novembre 2009 à 11:11, par vchahun

    Peut-être que des êtres humains à 9 doigts par main seraient intéressés par ce genre de billets (de banque !), mais je doute que ce soit le cas de la caissière moyenne de supermarché.

    Plus mathématiquement : Shallit a-t-il tenu compte dans son calcul du coût demandé pour trouver le nombre optimal de billets à rendre lors d’une transaction ou s’est-il contenté de trouver le nombre de billets optimal à échanger ?

    Répondre à ce message
    • Pièces et billets

      le 9 novembre 2009 à 08:58, par Jean-Paul Allouche

      Je ne suis pas sûr de comprendre ce que veut dire « le coût demandé pour trouver le nombre de billets optimal ». S’il s’agit de complexité d’algorithme (celui du rendu de monnaie), on peut se reporter à l’article de Shallit cité dans le billet, et sauf erreur cela ne dépend guère des valeurs faciales. S’il s’agit du temps de travail du commerçant pour calculer la monnaie à rendre, cela dépend de sa formation initiale, de sa maîtrise pratique d’un algorithme de rendu de monnaie, mais, comme l’expérience le montre (hélas ?), il n’y a plus grand monde pour rendre la monnaie à l’ancienne, la caisse enregistreuse donne automatiquement la monnaie à rendre : une légère adaptation lui ferait indiquer sous quelle forme rendre cette monnaie. Je m’amuse (hum le terme est un peu fort) parfois à introduire dans un distributeur automatique qui me demande disons 60 centimes, une pièce de 10 centimes puis une pièce d’un euro (dans cet ordre !) pour voir si je récupère une pièce de 50 centimes ou pas. Eh bien cela arrive...

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM