Trouver d'autres systèmes de pièces où le glouton échoue

def glouton_optimal_partout(pieces, jusqua=60):
    return all(len(rendu_monnaie(s, pieces)) == rendu_exhaustif(s, pieces)
               for s in range(1, jusqua + 1))

assert glouton_optimal_partout(EURO)
assert glouton_optimal_partout([25, 10, 5, 1])          # systeme americain
assert not glouton_optimal_partout([6, 4, 1])
assert not glouton_optimal_partout([25, 10, 1])         # sans la piece de 5

Le contre-exemple américain est spectaculaire.

assert len(rendu_monnaie(30, [25, 10, 1])) == 6      # 25 + 1 + 1 + 1 + 1 + 1
assert rendu_exhaustif(30, [25, 10, 1]) == 3         # 10 + 10 + 10

Six pièces contre trois, pour trente cents. Retirer une seule valeur d'un système canonique suffit à le faire cesser de l'être : la propriété tient au jeu tout entier, pas à chaque pièce prise isolément.

Une famille entière de mauvais systèmes.

mauvais = [p for p in range(3, 12)
           if not glouton_optimal_partout(sorted([p, p - 1, 1], reverse=True))]
assert mauvais == [4, 5, 6, 7, 8, 9, 10, 11]

Les systèmes $[p,p-1,1]$ échouent pour tout $p$ de $4$ à $11$ : deux pièces de $p-1$ valent presque $2p$, et le glouton, qui a pris un $p$, doit compléter à l'unité. Les systèmes où le glouton fonctionne ne sont donc pas la règle — ce sont des systèmes choisis.