Une condition nécessaire est que a et b soient premiers entre eux

C'est certainement suffisant si on accepte l'utilisation d'autres récipients pour servir" d'escale" .

Vasimolo

Avec des contenances x et y , il faut au moins que l'équation ax + by = 1 ait une solution entière à mon avis.

Ca exclut par exemple le cas de 2 contenances paires.

Réponse instinctive: il faut pgcd(a,b)=1

Approche demonstrative
soit k le pgcd, les recipients ont une contenance de kx et ky.
la différence des deux est k(x-y) etc. La plus petite quantité qui peut être obtenu est k.

Avec deux récipients de capacités A et B, il est impossible d'obtenir un volume strictement positif qui soit inférieur à d=PGCD(A,B).

Démonstration par invariant: les 2 récipients contiennent toujours une quantité de liquide multiple de d. C'est le cas quand ils sont vides tous les deux.
On notera une configuration où les  récipients contiennent A' et B' de la manière suivante: (A', B')
Depuis (A', B'), je peux:
- vider un récipient et passer en (0, B') ou en (A', 0)
- remplir un récipient entièrement depuis le robinet et passer en (A, B') ou en (A', B)
- transvaser entièrement un récipient dans l'autre (si c'est possible) et passer en (0, A'+B') ou en (A'+B', 0)
- transvaser récipient dans l'autre jusqu'à le remplir (si c'est possible) et passer en (A'-B+B', B) ou en (A, B'-A+A')
Comme A, B, A', B' et 0 sont des multiples de d; on a donc prouvé notre invariant.

On a donc montré qu'on ne peut pas avoir de volume entre 0 et PGCD(A,B)
On peut bien sûr avoir 0, montrons qu'on peut aussi avoir PGCD(A,B).

Tout d'abord, si A et B sont premiers entre eux (on notera A<B); on peut avoir 1cl.
En remplissant A et en le transvasant dans B jusqu'à le remplir; il me reste dans A une certaine quantité A'.
En répétant cette étape, il me reste 2A' (modulo A bien sûr), etc...
Or A' et A sont premier entre eux; en effet A'+B est un multiple de A (c'est ce qu'il me reste après avoir complété B en n'utilisant que des A) et A et B sont premiers entres eux
Du coup, la classe de A' engendre le groupe (Z/AZ, +)
Pour les non-initiés, ça veut juste dire que modulo A; en additionnant A' plusieurs fois; on trouve toutes les valeurs comprises entre 0 et A-1; donc 1 aussi.

On peut donc obtenir 1cl avec deux récipients si A et B sont premiers entre eux.
S'ils ne le sont pas, alors d=PGCD(A,B) donc A=m*d et B=n*d. En prenant comme unité non plus le centilitre mais le "d centilitres", on peut appliquer le même raisonnement: un récipient n et un autre m avec n et m premier entre eux: on peut donc obtenir une unité, soit d centilitres.

Conclusion: soient 2 récipients de capacités respectives A et B; le plus petit volume non nul qu'on puisse mesurer est PGCD(A,B)

Je dirais "a et b doivent être premiers entre eux", car il est clair, par exemple, qu'avec a et b pairs, on ne peut pas obtenir un volume impair à la fin. De manière générale, on ne pourra pas obtenir de volumes qui ne soient pas de la forme au+bv, donc pour pouvoir obtenir 1cL, on veut a et b premiers entre eux.

La réponse à la question "peut-on obtenir tous les au+bv inférieurs ou égaux à max(a,b) avec deux récipients de volumes a et b ?" m'échappe. Si oui, alors la condition nécessaire énoncée ci-dessus est suffisante.

C'est marrant je me suis posé la même question quand j'ai vu le problème initial, et j'ai juste intuité le résultat, là ça permet de pousser le raisonnement plus loin

Si a et b ne sont pas premiers entre eux, alors les quantités minimum que peuvent contenir les 2 récipients sont des multiples du pgcd de a et b.
En effet, on peut définir un invariant : les quantités dans les 2 récipients sont des multiples du pgcd de a et b.
. c'est le cas au début (0cl dans les 2 récipients)
. si on a une quantité dans les 2 récipients qui est multiple du pgcd de a et b, alors chaque récipient peut encore accueillir un multiple de ce pgcd :
  - si on remplit l'un des 2 (ou les 2, même si c'est idiot), on garde un multiple.
  - si on verse le contenu de l'un dans l'autre (jusq'au maximum, sinon on ne connait plus les quantités exactes), c'est toujours le cas aussi.
Donc on ne pourra jamais arriver à une quantité de 1cl si a et b ne sont pas premiers entre eux.

En revanche, quand a et b sont premiers entre eux, c'est possible, grâce à Bezout :
Il existe x et y, 0<x<b et 0<y<a tels que :
ax-by=1
Il suffit alors de remplir A, de le verser dans B, de vider B quand il est rempli, et de vider A dans B tant qu'il n'est pas vide, alors on arrivera au bout de x remplissages de x à 1cl.
On peut même optimiser :
(a-y)b-a(b-x)=1
Si b-x > (a-y), on préférera remplir B et le vider dans A (on fera moins d'opérations, fainéants que nous sommes !)

Dans l'exemple avec 33 et 20 :
5*20 - 3*33 = 1
C'est mieux que 17*33 - 28*20 = 1, comme j'avais fait au début, je m'étonnais de pas tomber rapidement sur 1cl, forcément avec 17 remplissages de canettes

Après une petite réflexion, j'en suis arrivé à un résultat un peu plus sympathique.

Tout d'abord, l'invariant dont je parlais plus haut montre clairement que toute quantité mesurée est un multiple de PGCD(A,B).

Autre point beaucoup plus intéressant, j'ajoute au problème les contraintes suivantes:
- je ne peux remplir un récipient que s'il est entièrement vide
- je ne peux vider un récipient que s'il est entièrement plein
On peut alors montrer, très simplement, qu'on peut obtenir les mêmes solutions que sans ces contraintes. En effet, on ne peut ajouter ou soustraire au volume total que a ou b.
Dans ce cas, le théorème de Bachet-Bézout nous dit qu'il existe toujours 2 entiers x et y tels que xA+bY = PGCD(A,B)
Par exemple, si x est positif et y négatif; cela signifie: "remplir A x fois; qu'on transvase dans B à chaque fois. On videra B dès qu'il est plein, y fois"
Bien entendu, n*x et n*y nous donnera n*PGCD(A,B) pour tout n (sous réserve bien sûr que n*PGCD(A,B) soit inférieur à A ou B)

On peut obtenir 1cl si et seulement si a et b sont premiers entre eux.
On convient que le récipient 1 est de a cl et le récipient 2 de b cl.

Prouvons que la condition est nécessaire.
En effet soit k un diviseur commun à a et b.
Alors par récurrence on montre aisément que les 2 récipients contiennent des multiples de k. Donc si l'on peut obtenir 1cl, on a k divise 1, c-à-d k=1.

Prouvons que la condition est suffisante.
a et b sont premiers entre eux donc ils satisfont à une relation de Bezout au+bv=1 avec u,v  entiers relatifs. On a donc aussi a(u+rb)+b(v-ra)=1 pour tout entier relatif r. Par suite il existe k entier >=1 tel que ka=1 modulo b.
La  méthode (qui n'est pas en général la plus rapide) consiste à verser continuellement le récipient 1 dans le récipient 2. Quand le récipient 2 est plein, on le vide. Quand le récipient 1 est vide, on le remplit avec l'eau du robinet.

Vasimolo a écrit:

Une condition nécessaire est que a et b soient premiers entre eux

C'est certainement suffisant si on accepte l'utilisation d'autres récipients pour servir" d'escale" .

Vasimolo

Je sais que j arrive en retard mais j'ai une question. Je considère que j'ai un récipient de 8 litres rempli (il sert de réservoir) et 2 récipients vide de 5 litres et 3 litres.

Est-ce que je peux justifier qu'on peut obtenir 1 litre (pgcd de 5 et 3) avec le théorème de Bézout et que si j'obtiens le pgcd qui est 1, je peux obtenir tous les multiples du pgcd donc tous les volumes compris entre 1 et 5?

Théorème de Bézout: au+ bv = pgcd (a;b)
a et b sont les contenances des deux récipients 5 et 3.
u représente le nombre de fois qu'on rempli un récipient et v représente le nombre de fois qu'on vide l'autre récipient.

Je me suis posé cette question parce que vous avez dit qu'il faut avoir deux récipient et un robinet mais je me disais que si les volumes des deux récipients sont premiers entre eux et que nous avons un 3ème qui est leur somme (8) plein, le théorème de Bézout peut également expliquer qu on obtient tous les volumes possibles.