L’Institut Monétaire de la Diophantie dont la monnaie est l’ouro (Ö), soucieux d’éviter la prolifération des pièces de monnaie, a émis une série limitée  de 12 pièces dont les valeurs faciales sont des entiers distincts d’ouros de telle sorte que n’importe quel montant entier de 1 ouro à N ouros – N fixé par décret – peut être payé avec 8 pièces ou moins, tout ou partie de ces pièces pouvant avoir la même valeur faciale.
Q₁ Sans l’aide d’un quelconque automate, trouver une série  de 12 pièces qui satisfait N = 6543 Ö (1).
Q₂ Avec l’aide d’un automate, trouver une série de 12 pièces qui satisfait N = 13000 Ö.
Q₃ Pour les plus courageux disposant d’un puissant automate : déterminer le plus grand entier N tel qu’il existe au moins une série de 12 pièces distinctes telles que toute somme comprise entre 1 et N inclus peut être réglée avec au maximum 8 pièces pas nécessairement distinctes.

(1)Cette question est le problème n°3 posé aux candidats du niveau 11 des Olympiades russes de mathématiques au printemps 2013. C'est une variante du problème bien connu du timbre-poste. Une documentation abondante en anglais (« Postage Stamp problem ») est disponible sur Internet.

 Solution

Pierre Henri Palmade, Jean Nicot et Bernard Vignes  les uns et les autres avec des approches différentes ont répondu à la première question sans faire appel à un automate.
S'agissant de la deuxième question, la palme revient à Christian Boyer qui obtient un très beau score de 19621 avec la séquence 1, 8, 13, 58, 169, 295, 831, 1036, 1864, 3162, 7005, 8182 dont les huit premiers termes sont donnés dans l'article Some Extremal Postage Stamp Bases de Michael F. Challis.