Du stehst an einem Brunnen und hast zwei unskalierte Kannen: eine fasst genau 5 Liter, die andere genau 3 Liter. Du kannst beliebig oft Kannen ganz füllen, ganz ausleeren oder aus einer in die andere umfüllen, bis entweder die Quelle leer oder das Ziel voll ist.
Miss damit genau 4 Liter ab.
Beschreibe einen Zustand als Paar $(a, b)$ der Füllstände. Welche Zustände sind von $(0,0)$ aus erreichbar?
Die Lösung ist ausgeblendet. Nimm dir erst selbst Zeit für die Aufgabe – der Aha-Moment lässt sich nicht nachholen.
Hast du es ernsthaft versucht – und den Hinweis gelesen? Danach gibt es kein Zurück im Kopf.
Lösung
Wir notieren den Zustand als $(a, b)$ mit $a$ Litern in der 5er- und $b$ Litern in der 3er-Kanne.
| Schritt | Aktion | Zustand |
|---|---|---|
| – | Start | $(0,0)$ |
| 1 | 5er füllen | $(5,0)$ |
| 2 | 5er in 3er umfüllen | $(2,3)$ |
| 3 | 3er ausleeren | $(2,0)$ |
| 4 | 5er in 3er umfüllen | $(0,2)$ |
| 5 | 5er füllen | $(5,2)$ |
| 6 | 5er in 3er auffüllen | $(4,3)$ |
Im letzten Schritt passt nur noch 1 Liter in die 3er-Kanne, also bleiben genau 4 Liter in der grossen Kanne zurück. Kürzer geht es nicht – sechs Schritte sind das Minimum.
Es geht auch über die kleine Kanne – dieser Weg ist länger:
Hier sind es acht Schritte statt sechs. Der Umweg führt über den Zustand $(1,0)$: Hat man erst einmal 1 Liter abgemessen, genügt eine volle 3er-Kanne obendrauf.
Jede Aktion ändert die Gesamtmenge um ein Vielfaches von 5 oder 3. Erreichbar sind daher genau die Mengen der Form $5x + 3y$ mit $x, y \in \mathbb{Z}$, soweit sie in eine Kanne passen. Da $\gcd(5,3) = 1$ ist, liefert das Lemma von Bézout alle ganzen Zahlen – konkret ist
also „dreimal die 3er-Kanne einfüllen, einmal die 5er-Kanne wegschütten", was genau dem zweiten Weg oben entspricht. Mit einer 4er- und einer 6er-Kanne wäre die Aufgabe dagegen unlösbar: $\gcd(4,6) = 2$, und aus geraden Mengen lässt sich nie eine ungerade erzeugen.