Wenn Sie einen Versuch machen wollen, klicken Sie auf die gezeichneten Fässer.
Das dritte Gefäß (8 Liter) ist anfangs voll und
die ersten zwei Gefäße sind anfangs leer.
Wir stellen uns eine allgemeinere Frage.
Gesetzt, ich habe 3 Gefäße
von Fn-1, Fn und Fn+1
Litern. Kann ich dann durch mehrmaliges Umfüllen jede Menge an ganzen
Litern abmessen, bis zu einem Maximum von Fn+1 Litern?
Diese Frage wollen wir
jetzt beantworten.
Nach maximal zweimaligem
Umfüllen können wir die nächste triviale Lage erreichen: Die
ersten zwei Gefäße sind beide leer oder beide voll oder eines der beiden ist leer und
das andere ist voll. Wir versuchen die uninteressanten trivialen Lagen (wenn
möglich) zu vermeiden.
Bemerke dass jeder
Umfüllvorgang gekennzeichnet wird durch eine der nächsten Situationen.
Das Gefäß womit
man giesst, wird völlig geleert, oder: ein anderes Gefäß wird völlig gefüllt.
Kurz, immer ist ein Gefäß leer und/oder ein Gefäß voll.
Wenn ein Gefäß voll
ist, muss man damit gießen, denn sonst entsteht eine 'triviale Lage'.
Ist ein Gefäß leer, dann muss in dieses Gefäß gegossen werden, schon wieder um eine 'triviale
Lage' zu vermeiden.
Die Anfangssituation ist besonder, denn 2 Gefäße sind dann leer. Wir haben die Wahl und füllen das dritte Gefäß um in das zweite. (Die Alternative ist gleich gut). Ab diesem Moment liegt jeder Umfüllvorgang eindeutig fest (wenn wir uns halten an oben erwähnten Regeln: Fülle immer mit einem vollen Gefäß und fülle ein leeres Gefäß; und wenn wir nie den letztgespielten Umfüllvorgang zurüchdrehen).
Wir gehen Inductiv vor.
Gesetzt, eines Augenblickes
enthält das erste Gefäß a Liter und Gefäß 2 ist leer. Die vorangehende
Handlung war das Umfüllen dieser a Liter von Gefäß 2 in Gefäß 1.
Bemerke dass in der
Anfangssituation gilt: a=0.
Lage Schritt x:
a ... 0 ... b (=Fn+1-a)
Im nächsten Schritt
wird das leere Gefäß gefüllt, und die a Liter nicht zurückgegossen, also wird
das Resultat
Schritt x+1: a ...
Fn ... b-Fn
Nun das volle Gefäß
gebrauchen und nicht zurüchgiessen. Das gibt:
Schritt x+2: Fn-1
... a+Fn-2 ... b-Fn
Nun das volle Gefäß
gebrauchen und nicht zurückgiessen. Das gibt:
Schritt x+3: 0 ...
a+Fn-2 ... b-Fn-2
Ins leere Gefäß
giessen und nicht zurückgiessen. Jetzt können 2 Situationen entstehen, nämlich
wenn a+Fn-2 < Fn-1, dann:
Schritt x+4: a+Fn-2
... 0 ... b-Fn-2
und anders:
Schritt x+4: Fn-1
... a-Fn-3 ... b-Fn-2
gefolgt von
Schritt x+5: 0 ...
a-Fn-3 ... b+Fn-3
und da a <=
Fn-1 (sieh Anfangssituation)
Schritt x+6: a-Fn-3
... 0 ... b+Fn-3
Wir sind nach 4 a 6
Schritte wieder in eine ähnliche Lage geraten, aber dabei enthält das erste
Gefäß Fn-2 Liter mehr oder, wenn das Gefäß dazu zu klein
ist, Fn-3 Liter weniger.
Folgerung: Das erste
Gefäß ist immer leer oder voll oder enthält kFn-2-mFn-3
Liter, für gewisse nicht negative ganze Zahlen k und m.
Wir wollen die Folgerung
umdrehen. Mit anderen Worten, wenn k und m nicht negative ganze Zahlen
sind und t = kFn-2-mFn-3, ist positiv
und kleiner als Fn-1, wird es dann nach einigen Umfüllungen
t Liter geben im ersten Gefäß?
Wohlan, nach ein Paar
Umfüllungen wird m mal Fn-3 aus dem ersten Gefäß gegossen
sein. Dann gibt es noch sage k1Fn-2-mFn-3
Liter im ersten Gefäß. Nun ist k1 = k oder k1 = k+1 oder k1 = k-1 (denn 2Fn-2>Fn-1).
Wenn k1 = k, dann kann t Liter entstehen. Wenn k1 = k+1, dann gibt es t+Fn-2
Liter im Gefäß. 4 a 6 Schritte vorher ist entweder Fn-2
hinzugekommen und wir hätten dann t Liter im ersten Gefäß, oder Fn-3
Liter ist angezapft und damals waren t+Fn-2+Fn-3
Liter im ersten Gefäß. Aber das ist unmöglich denn das is mehr als was das erste Gefäß enthalten kann.
Wenn k1 = k-1, dann
haben wir t-Fn-2 Liter im ersten Gefäß. Noch 4 Schritte weiter und
wir haben t Liter im ersten Gefäß.
Um den Beweis, dass jede Menge an Litern abgefüllt werden kann, zu vervollständigen benützen wir die nächste Allgemeinformel für Fibonaccizahlen.
(-1)pFq-p = Fp-1Fq - FpFq-1
Substituiere q=n-2
und, wenn n gerade ist p=n-3, und wenn n ungerade ist p=n-4. Das gibt:
1 = Fn-4Fn-2
- Fn-3Fn-3 wenn n ungerade ist und
1 = Fn-5Fn-2
- Fn-4Fn-3 wenn n gerade ist.
Wir sehen dass 1 zu
schreiben ist als kFn-2-mFn-3 mit k
und m nicht negative ganze Zahlen. Also ist das auch der Fall für jede
Zahl zwischen 1 und Fn-1
Also nach einigen
Schritten ist das erste Gefäß gefüllt mit t Litern (für jedes t mit 0 <= t <= Fn-1).
t Liter im ersten Gefäß
und Fn Liter im zweiten gibt im nächsten Schritt t2
= t+Fn-2 Liter im zweiten Gefäß, und t2 kann jeden Wert annehmen
zwischen Fn-2 und Fn.
Fn+1-t
ist eine Zahl zwischen Fn und Fn+1. Kurz,
jede ganze Anzahl an Litern bis zu einem Maximum von Fn+1 kann
abgefüllt werden.