Zwei Eimer/Teilerfremd/Aufgabe/Lösung

Ohne Einschränkung sei ${}a\leq b$. Wir bezeichnen die Inhalte in den Eimern zu einem bestimmten Zeitpunkt in Paarschreibweise mit ${}(u,v)$, wobei ${}u$ zwischen ${}0$ und ${}a$ und ${}v$ zwischen ${}0$ und ${}b$ liegt. Es sei ${}r$ der Rest von ${}-b$ bei Division durch ${}a$. Wir behaupten, dass wenn man die Belegung ${}(u,0)$ durch die erlaubten Schritte erzielen kann, dass man dann auch ${}(u',0)$ erzielen kann, wobei ${}u'$ den Rest von ${}u+r$ modulo ${}a$ bezeichnet. Wir starten also mit

$(u,0).$

Durch Umschüttung kann man

$(0,u)$

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

$(0,u+a)$

erreichen, und ebenso der Reihe nach

$(0,u+2a),\,(0,u+2a),\ldots ,(0,u+ka),$

wobei ${}k$ so gewählt sei, dass

${}u+ka\leq b\,$

und

${}u+(k+1)a>b\,$

sei. Von hier aus erreichen wir

$(a,u+ka).$

Wir füllen nun den Inhalt des ersten Eimers in den zweiten, bis dieser voll ist. Es sei ${}m$ die umgefüllte Menge. Diese erfüllt

${}u+ka+m=b\,.$

Die im ersten Eimer verbleibende Wassermenge ist somit

${}a-m=a-(b-u-ka)=u+(k+1)a-b\,.$

Diese Menge ist also der Rest von ${}u-b=u+r$ modulo ${}a$, wie behauptet.

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

$(0,0),(r,0),(2r,0),(3r,0),\ldots .$

Da ${}b$ teilerfremd zu ${}a$ ist, gibt es nach dem Lemma von Bezout positive ganze Zahlen ${}n,m$ mit

${}ma-nb=1\,$

(Falls ${}n,m$ negativ sind, betrachtet man einfach ${}(sb+m)a-(sa+n)b=1$ für ein ausreichend großes ${}s$).

Somit ist modulo ${}a$

${}nr\equiv -nb=1-ma=1\,,$

so dass bei Division durch ${}a$ für ein gewisses ${}n$ der Rest von ${}nr$ gleich ${}1$ ist.

Zur gelösten Aufgabe