Désolé je me suis mal exprimé.

Voila, cela doit être bon...

Quand a et b sont premiers entre eux, on sait que l'équation [latex]au+bv=c[/latex] a une infinité de solutions, mais si u>0 on a souvent v<0 et ça ne marche pas avec les pièces...

La formule pour u est [latex]u=u_0+kb[/latex] avec [latex]0\le u_0<b[/latex] , associée à [latex]v=v_0-ka[/latex].
Alors [latex]au_0<ab[/latex].
S'il décide de payer [latex]c+ab[/latex], il donne [latex]u_0[/latex] pièces de a € et [latex]v_0+a[/latex] pièces de b €, cette dernière était forcément positive.
Je propose donc qu'il majore chaque somme de la valeur [latex]ab[/latex] et tout est possible.
On doit pouvoir faire un peu mieux mais ce n'est pas la question...

Je comprends un peu mieux du coup: la question est en fait de savoir si l'ensemble des prix "impayables" est fini.

Démonstration de l'équivalence des deux questions:
Si je peux trouver une telle somme S et que l'ensemble des prix impayables n'est pas fini, alors il existe un prix impayable P > S. Du coup, P-S est un prix qui, si on lui ajoute S, est impayable; ce qui est absurde.
Réciproquement, si l'ensemble des prix impayables est fini, alors il admet un PGE noté S. Pour tout prix P>0, P+S > S donc P+S est payable

On note P et Q nos 2 valeurs de pièces.
On remarque que si je peux payer S, alors je peux payer S+P
Du coup, si j'ai P sommes payables consécutives, alors toutes les sommes supérieures sont payables elles aussi.
Le théorème de Bachet-Bézout nous indique qu'il existe a et b tels que aP+bQ = 1
a et b sont nécessairement de signes contraires, on posera a > 0 (sinon on reprend le même raisonnement en remplaçant P par Q)
Dans ce cas, X=-bPQ est payable (b est négatif)
De même, X+1 =-bPQ+1 = aP -b(P-1)Q est payable (P>1)
Plus généralement pour tout j < P, X+j = ajP -b(P-j)Q est payable
Du coup, toutes les sommes allant de X à X+p sont payables et toutes les suivantes aussi.

Notre homme a donc une solution: il résout aP+bQ = 1 via l'algorithme d'Euclide étendu, il prend le terme négatif parmi a et b et il le multiplie en valeur absolue par PQ. Tout prix ajouté à cette somme est alors payable

Avec 2 types de pièces dont les valeurs faciales n et m sont premières entre elles, le montant le plus important que l'on ne puisse pas payer est: (n-1)(m-1)-1.
Exemple: 3 et 7: on ne peut pas payer 11 et c'est le plus grand montant.

Il suffit donc qu'il choisisse (n-1)(m-1)-1 comme somme fixe à ajouter.
En effet on ne lui demandera jamais de payer 0. Et à partir de 1, la somme à payer sera toujours au moins égale à (n-1)(m-1) qui est payable avec des pièces de n et m.

J'ai eu du mal à comprendre l'énoncé. J'espère avoir compris.

Merci pour l'énigme.

Je l'ai trouvé sympa, juste un peu dur à comprendre avant ta clarification.
Mais n'hésite pas à en créer d'autres. Je trouve ça plus sympa.

Comme j'ai quelques minutes, je vais démontrer le résultat que j'ai balancé ci-dessus pour ceux que ça intéressent

Soit m et n premiers entre eux.
On veut montrer qu'à partir de P=(n-1)(m-1) toutes les sommes sont payables, c'est-à-dire qu'il existe a et b positifs ou nuls tels que P=an+bm.

Regardons les m valeurs P-0.n, P-1.n, P-2.n, ..., P-(m-1)n dans Zm (Z/mZ).
Puisque n et m sont premiers entre eux et qu'il y en a m consécutives, ces valeurs sont toutes différentes dans Zm donc l'une d'entre elle vaut 0, c'est-à-dire est congrue à 0 modulo m, c'est-à-dire qu'il existe b tel que cette valeur soit égale à bm. Soit a l'entier tel que P-an=bm. a est positif puisque compris par construction entre 0 et m-1. Il reste à montrer que b est aussi positif.
[TeX]P-an=nm-n-m+1-an\ge nm-n-m+1-(m-1)n \ge -m+1[/TeX]
Or P-an est divisible par m et est supérieur ou égal à -m+1. Cette valeur est donc supérieure ou égale à 0 (aucun entier entre -m+1 et 0 ne sont divisible par m).
Donc bm=P-an est supérieur ou égal à 0 donc b aussi CQFD.

On peut aussi montrer que (n-1)(m-1)-1 n'est jamais payable avec un raisonnement similaire: (n-1)(m-1)-1=(m-1)n-m et on ne peut jamais compenser le -m pour rendre le facteur de n et de m positifs.

Il y a 1 ou 2 ans, un problème plus général à été posé lors de la finale du championnat FFJM.
On choisissait 4 nombres a, b, c, d tels que:
P1=abc
P2=abd
P3=acd
P4=bcd
soient premiers entre eux.
Et il fallait trouver la plus grande somme non payable avec a, b, c et d.
Il me semble me souvenir que le résultat est 3abcd-P1-P2-P3-P4.
En posant c=d=1, on trouve 3ab-ab-ab-a-b ce qui redonne le résultat pour 2 valeurs avec la même conditions de primalité.
Avec d=1, on trouve: 2abc-ab-ac-bc avec ab, ac et bc premiers entre eux.