Zwei Eimer/Teilerfremd/Aufgabe/Lösung

Ohne Einschränkung sei  $a\le 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, man dann auch $(u^{\prime },0)$ erzielen kann, wobei $u^{\prime }$ 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),\dots ,(0,u+ka),$

wobei $k$ so gewählt sei, dass

$u+ka\le 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 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),\dots .$

Da $b$ teilerfremd zu $a$ ist, gibt es nach dem Lemma von Bézout 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,$

sodass bei Division durch $a$ für ein gewisses $n$ der Rest von $nr$ gleich $1$ ist.

Zur gelösten Aufgabe