Un glouton qui se trompe de deux pièces

Système $[5,4,1]$, somme $8$.

Le glouton prend la plus grosse pièce possible à chaque étape : $5$, puis il reste $3$, sur quoi $4$ ne passe pas, donc $1+1+1$. Total : $5+1+1+1$, soit 4 pièces.

L'optimal est $4+4$, soit 2 pièces. Le glouton fait deux fois trop.

Pourquoi il échoue. Il choisit ce qui paraît le meilleur sur le moment et ne revient jamais en arrière. Prendre $5$ laisse un reste de $3$ que le système paie très mal ; renoncer à la grosse pièce aurait été payant. Aucun raisonnement local ne peut le voir.

Ce qui sauve le système euro. Les systèmes $[1,2,5,10,20,50,\dots ]$ sont dits canoniques : pour eux, le glouton est optimal, et cela se démontre. Ce n'est donc pas la méthode qui est bonne, c'est le système qui est bien choisi — et le programme officiel demande précisément de savoir distinguer les deux.