Problème des deux récipients

On considère le problème classique de deux récipients de 7 litres et 5 litres, à côté d'un source d'eau. Les récipients ne sont pas gradués. Tout ce qu'on peut faire ses les remplir à ras-bord, les vider, les transvaser l'un dans l'autre.

Le but du jeu est d'obtenir, dans un des récipients, un certain volume prédéfini, par exemple 3 litres.

On indique l'opération effectuée et le contenu de chaque récipient à chaque étape.

On peut prouver que si $d$ est le PGCD des deux capacités – ici 5 et 7, donc $d = 1$ – on pourra obtenir tous les volumes en $k\cdot d$ inférieurs ou égaux à la capacité max.

Autrement dit ici, on peut obtenir tous les volumes : 0, 1, 2, 3, 4, 5, 6, 7 litres.

On se donne deux récipients de capacité A et B. On souhaite obtenir le volume V.

Ces trois nombres sont entiers positifs.

On veut

• savoir si c'est possible,
• et, si c'est possible, la séquence avec le moins d'opérations permettant d'atteindre le résultat voulu.

Une façon d'arriver au résultat est de poser un graphe.

Dans l'exemple proposé il était possible, depuis une situation où le premier récipient contient 7L et le second 2L, de vider le premier dans le second pour obtenir 4L et 5L.

On pourrait résumer cela en (7,0) → (4,5).

On reconnaît deux nœuds de graphe reliés par une arête.

Le graphe correspondant est donné ci-dessous.

• En violet, les arêtes à sens unique, on doit pouvoir résoudre le problème sans les utiliser.
• En bleu le chemin menant de 0, 0 à un une position où un des récipients contient 3L.