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.