Zwei Eimer/Teilerfremd/Aufgabe/Lösung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Ohne Einschränkung sei . Wir bezeichnen die Inhalte in den Eimern zu einem bestimmten Zeitpunkt in Paarschreibweise mit , wobei zwischen und und zwischen und liegt. Es sei der Rest von bei Division durch . Wir behaupten, dass wenn man die Belegung durch die erlaubten Schritte erzielen kann, dass man dann auch erzielen kann, wobei den Rest von modulo bezeichnet. Wir starten also mit

Durch Umschüttung kann man

erreichen. Durch Auffüllen des kleinen Eimers und anschließende Umfüllung in den großen kann man

erreichen, und ebenso der Reihe nach

wobei so gewählt sei, dass

und

sei. Von hier aus erreichen wir

Wir füllen nun den Inhalt des ersten Eimers in den zweiten, bis dieser voll ist. Sei die umgefüllte Menge. Diese erfüllt

Die im ersten Eimer verbleibende Wassermenge ist somit

Diese Menge ist also der Rest von modulo ,wie behauptet.

Aufgrund von dieser Beobachtung können wir der Reihe nach folgende Belegungen erzielen (bzw. die Reste davon modulo a).

Da teilerfremd zu ist, gibt es nach dem Lemma von Bezout positive ganze Zahlen mit

(Falls negativ sind, betrachtet man einfach für ein ausreichend großes ).

Somit ist modulo

so dass bei Division durch für ein gewisses der Rest von gleich ist.
Zur gelösten Aufgabe