Wie kann man 4 Liter mit 8-, 5- und 3- Litergefäßen abmessen?
Es geht um die seit Jahrhunderten bekannte Aufgabe: Gegeben ist ein
volles 8-Litergefäß und je ein leeres 5-- und 3--Litergefäß. Kann man
damit 4 Liter abmessen? Solche Aufgaben tauchen in den verschiedensten
Situationen immer wieder auf. So hatten zum Beispiel Bruce Willis und
Samuel L. Jackson im Film "Stirb langsam: Jetzt erst recht" (der mit den
Goldbarren) eine ähnliche Aufgabe zu lösen. Höchste Zeit also, dieses
Problem mathematisch zu untersuchen.
Ziel einer mathematischen Behandlung ist die Entwicklung
eines Algorithmus, mit dem sich nicht nur diese Aufgabe lösen läßt,
sondern mit dem die Lösung für beliebige Gefäße mit beliebigen
Anfangswerten (Füllstand der Gefäße) und beliebigen Zielmengen
gefunden werden kann.
Mathematisch läßt sich der augenblickliche Zustand des Systems durch die
Füllmenge (x,y,z), also einen Punkt im dreidimensionalen Raum
darstellen. Aber x, y und z müssen natürliche Zahlen
sein und
erfüllen eine Erhaltungsgleichung x+y+z=V (konstante
Gesamtflüssigkeitsmenge). Dadurch
läßt sich das Problem geometrisch in einem
regulären Dreiecksgitter auf der Ebene und doch mit drei
Koordinatenachsen veranschaulichen.
Operationen (gieße ein Gefäß in ein anderes) sind
Wege auf diesem Dreiecksgitter. Bei der Untersuchung dieser
Operationen stellt man fest, daß es vorwärts stets mehrere Möglichkeiten
gibt (welches Gefäß gieße ich wohin), rückwärts aber nur eine. Es ist
also sinnvoll -- wie bei vielen Problemen aus der Spieltheorie --,
das Problem rückwärts zu lösen: Aus welchen Anfangszuständen ist eine
Erreichung des Endzustandes möglich? Dieses -- im Gegensatz zum
ursprünglichen -- nun deterministische Problem ist der Bewegung einer
Billardkugel in einem konvexen n-Eck auf einem regulären Dreicksgitter
äquivalent. Die Klassifizierung der möglichen konvexen n-Ecke auf so
einem Gitter führt zu einer allgemeinen Lösung des obigen Problems.
Die Folien zum Vortrag auf dem Tag der Mathematik am 19. Mai 2001 gibt es hier: