Ein altes Problem und der PERELMANsche Papiercomputer

          Die Lösung steht im unteren Teil der Seite.

Eine schon lange bekannte Problemstellung lautet beispielhaft so:

Aus einem Wasserbehälter sollen 3 Liter entnommen werden. Es sind aber nur zwei Krüge mit 7 bzw. 9 Liter Volumen zur Hand.

Wir haben es also mit der Klasse der Umfüllprobleme zu tun. Durch eine endliche Anzahl von Umfüllvorgängen zwischen dem Wasserbehälter und den beiden Krügen (die natürlich keine Skalen zur Ablesung eines Teilvolumens aufweisen) soll eine vorgegebene Menge abgemessen werden. Natürlich sind die Volumina 3, 7, 9 willkürlich gewählt und können ganz andere Werte annehmen. Das gewählte Beispiel ist nicht ganz einfach, immerhin benötigt man acht Umfüllvorgänge, um 3 Liter abzumessen. Unterstellt wird dabei, dass der Behälter genügend viel Wasser enthält, das heißt in der Regel mindestens soviel, wie in beide Krüge zusammen passt. Manchmal findet man aber solche Probleme auch in der abgewandelten Form, dass der Behälter ein dritter Krug mit bekanntem Volumen ist.

Wie löst man ein solches Problem? In Büchern mit mathematischen Rätseln werden fast immer nur die einzelnen Umfüllschritte angegeben, aber es wird nicht klar, ob die Lösung die kürzeste ist oder sogar eindeutig; vor allem ist meist keine Systematik erkennbar. Man hat den Eindruck, dass es auf Intuition oder geschicktes Ausprobieren ankommt. Tatsächlich ist das aber nicht so: Es gibt im wesentlichen nur einen Lösungsweg, und die einzelnen Umfüllschritte folgen einer sehr einfach zu merkenden Regel.

Hier kommt der weißrussische Wissenschaftler Yakov Isidorovich Perelman (1882 - 1942) ins Spiel. Perelman studierte Forstwissenschaften in St. Petersburg und erhielt dort eine fundierte Ausbildung in Mathematik und den Naturwissenschaften. Ab 1918 arbeitete er für die sowjetrussische Nationale Kommission für Ausbildung. Sein lebenslanges Hauptinteresse lag in der Vermittlung von Mathematik, Astronomie, Physik und Technik für ein breites Publikum. Perelmans Bibliographie umfasst Hunderte von Fachartikeln und Büchern. Sein schriftstellerischer Erfolg beruhte auf seiner Fähigkeit, wissenschaftliche Inhalte verständlich und fesselnd darzustellen. Populärwissenschaftliche Publikationen wie z.B. "Algebra zur Unterhaltung" und "Lebendige Mathematik" haben bis heute zahllose Auflagen erlebt und sind in viele Sprachen übersetzt worden.

  Y. I. Perelman


Yakov Isidorovich Perelman darf nicht mit einem anderen russischen Mathematiker verwechselt werden. Sein Namensvetter  -  aber nicht mit Yakov verwandt  -  Grigorij Yakovlevich Perelman (geb. 1966) ist einer der renommiertesten Mathematiker der Gegenwart, weil er die Poincaré'sche Vermutung bewiesen hat. Am 22. August 2006 wurde ihm auf dem Internationalen Mathematiker-Kongress in Madrid die Fields-Medaille verliehen. G. Y. Perelman, der als höchst exzentrisch gilt, erschien nicht zum Kongress und lehnte die Ehrung ab.


Schon zu Y. I. Perelmans Zeiten war das Umfüllproblem nicht neu. Aber er hatte eine gute Idee. Er stellte das Problem und seine Lösung auf geschickte Weise graphisch dar. Wir wollen die folgende Notation einführen:  n  bzw.  m  (Liter) seien die (ganzzahligen) Volumina der beiden Krüge,  k  die (ganzzahlige) abzumessende Menge. Mit (a,b) bezeichnen wir den jeweiligen Füllungsstand der beiden Krüge. Man beginnt also bei (0,0) und hat als Ziel (k,b) oder (a,k). Perelman zeichnete nun alle Füllungsstände (a,b) mit ganzzahligen  0 ≤ a ≤ n  und  0 ≤ b ≤ m  als Gitternetz in ein Koordinatensystem. Aus Gründen, die wir noch erkunden werden, ist sein Koordinatensystem aber nicht rechtwinklig, sondern die positiven Achsen bilden einen Winkel von  60°. So sieht das Gitternetz für  n = 5  und  m = 3  aus:



Die Punkte in diesem Gitternetz werden jetzt so verbunden, dass ein Raster aus gleichseitigen Dreiecken entsteht. Man beachte, dass jede gerade Linie von Rand zu Rand einem Umfüllvorgang entspricht (grüne Linie im nächsten Bild als Beispiel). Dieses Gebilde nennen wir Perelman'scher Papiercomputer, denn er wird uns alle Arbeit bei der Lösung des Umfüllproblems abnehmen. Die Beschriftung der inneren Punkte lassen wir ab jetzt fort, denn wir werden noch sehen, dass sie später nicht mehr benötigt werden.



Genau genommen entspricht die grüne Linie zwei Umfüllvorgängen: Von unten links nach oben rechts wird der leere kleine Krug aus dem Behälter gefüllt (mit 3 Litern), von oben rechts nach unten links wird er in den Behälter entleert; in beiden Fällen bleibt der große Krug mit 4 Litern Inhalt unverändert.

Wie funktioniert nun dieser Papiercomputer?
Beginnend bei (0,0), geht man zu (0,3) oder zu (5,0) und von dort auf einem Zickzackweg, immer entlang gerader Linien von Rand zu Rand, bis man an einem Punkt angekommen ist, der die abzumessende Menge  k  darstellt. Der Grund für die  60°-Neigung der senkrechten Achse wird jetzt deutlich: Stößt man im Papiercomputer an einen Rand, so verläuft der weitere Weg nach dem optischen Prinzip "Einfallswinkel = Ausfallswinkel" (dieser Winkel ist hier immer  60°).

Ein Beispiel: Die beiden Krüge fassen 5 bzw. 3 Liter; 4 Liter sind abzumessen:


Papiercomputer löst  n = 5, m = 3, k = 4 

Wir führen eine Notation für die Umfüllschritte ein:

G   großer Krug
K   kleiner Krug
"füllen" :  aus Wasserbehälter auffüllen
"leeren" :  in Wasserbehälter ausleeren
"umfüllen" :  maximal mögliche Menge von einem Krug in den anderen umfüllen

Welche Umfüllungen entsprechen der gezeigten Lösung?

(5,0)   G füllen
(2,3)   G nach K umfüllen
(2,0)   K leeren
(0,2)   G nach K umfüllen
(5,2)   G füllen
(4,3)   G nach K umfüllen

Es wurden also sechs Umfüllschritte benötigt. Hätte man zuerst den kleinen Krug gefüllt, wäre man in acht Schritten zu (4,0) gelangt.

Bevor wir uns mit der mathematischen Systematik des Perelman'schen Papieromputers befassen, soll noch das einleitende Beispiel gelöst werden:



Papiercomputer löst  n = 9, m = 7, k = 3 


Nun wissen wir, wie der Perelman'sche Papiercomputer funktioniert. Man markiert die Randpunkte mit  a = k  oder  b = k  (im Bild grün unterlegt) und probiert die beiden Wege über (0,m) und (n,0) aus  -  einer davon ist der kürzeste. Wir wollen einige Punkte festhalten, die an der Perelman'schen Idee auffallen:

Dass der Perelman'sche Papiercomputer so schön funktioniert, soll uns anregen, ihn genauer zu analysieren. Natürlich stellen sich Fragen ein: Ist das Perelman'sche Verfahren für alle  n, m, k  anwendbar? Ist es das schnellste Verfahren oder sogar das einzige?

Es soll im folgenden  n > m > 1  und  n > k ≥ 1  gelten, denn mit gleich großen Krügen kann man das Problem offensichtlich nicht lösen, und ein Krug mit 1 Liter Volumen erlaubt trivialerweise die Abmessung von  k  Litern und wird deshalb nicht zugelassen.

Zum Auftakt wird eine Frage zur Struktur des Papiercomputers gestellt, dann folgt Schritt für Schritt der Beweis zur "Rechtfertigung" des Papiercomputers:

Aufgabe 1
Wenn man den Papiercomputer in ein rechtwinkliges Koordinatensystem transformiert, fällt eine Asymmetrie auf. Wie lässt sich diese erklären? (Gerade diese Asymmetrie erlaubt die regelmäßige "Pflasterung" des Papiercomputers mit gleichseitigen Dreiecken.)

Aufgabe 2
Wie verlaufen die beiden ersten Umfüllschritte sinnvollerweise? Vergleichen Sie dies mit dem Papiercomputer.
Wann endet das Verfahren?  (Vorsicht: Wir wissen (bisher) noch nicht, ob  a = k  oder  b = k  immer erreicht wird.)

Aufgabe 3
Zeigen Sie:
Nach jedem Umfüllschritt ist ein Krug leer oder ein Krug voll.  (Vollständige Induktion.)
Ist entweder ein Krug leer oder ein Krug voll, so gibt es genau vier Umfüllmöglichkeiten, aber nur eine davon ist sinnvoll.  Als Nebenresultat erhält man: Jede Umfüllaktion lässt sich rückgängig machen.
Beschränkt man sich auf sinnvolle Umfüllungen, so ist nach dem zweiten und vor dem letzten Umfüllen immer entweder ein Krug leer oder ein Krug voll.
Machen Sie sich klar: Dies ist der Beweis, dass der Perelman'sche Papiercomputer das einzig mögliche Umfüllverfahren beschreibt. Insbesondere werden damit der erste und der vierte Punkt von (1) verständlich.
Beschreiben Sie die verschiedenen Umfüllmöglichkeiten formal, indem Sie (a,b) vor und nach dem Umfüllen angeben. Vergleichen Sie dies mit dem Papiercomputer. Formulieren Sie aber auch eine einfache verbale Regel, anhand der man ohne Papiercomputer die sinnvollen Umfüllschritte durchführen kann.


Wir halten einen Moment inne. Was haben wir bis hierhin gezeigt?

Was fehlt noch? Wir wissen noch nicht, wann das Umfüllproblem überhaupt lösbar ist, d.h. welche  n, m, k  eine Lösung erlauben. Diese Frage ist völlig unabhängig vom Papiercomputer, aber dieser wird uns helfen, die Antwort zu veranschaulichen. Wir begeben uns jetzt auf das Gebiet der Zahlentheorie.


Aufgabe 4
Sind  n  und  m  nicht teilerfremd, so ist das Umfüllproblem nicht für alle  k  lösbar.  Verwenden Sie die Aufgaben 2 und 3 und zeigen Sie damit die Behauptung induktiv.


n  und  m  seien also ab hier teilerfremd. Testläufe mit dem Perelman'schen Papiercomputer legen nahe, dass dann jedes  k  erreicht wird (siehe den zweiten Punkt in (1)). Genauer: Es gibt, beginnend mit (0,m), genau einen Weg durch den Papiercomputer, endend bei (n,0); dieser Weg trifft jeden Randpunkt außer (0,0) und (n,m) genau einmal. Der andere Weg beginnt bei (n,0), endet bei (0,m) und ist lediglich die Umkehrung des ersten (siehe den dritten Punkt in (1)). Es gibt nun einen kleinen Trick, um sich die Beweisidee zu veranschaulichen. Beginnt man bei (0,m), so beschreibt der Lösungsweg im Papiercomputer eine Zickzacklinie, bis er auf den rechten Rand trifft. Da er dann zum linken Rand überspringt, liegt es nahe, für den weiteren Lösungsweg den Papiercomputer rechts als Kopie anzulegen; dann entfällt der "Übersprung" von rechts nach links und der Lösungsweg bildet eine duchgehende Zickzacklinie. Man legt soviele Kopien rechts an, bis der Punkt (n,0) erreicht ist. Das soll für  n = 5  und  m = 3  veranschaulicht werden:



Die roten Linien in diesem Bild sind die "Nahtlinien". Der Schnittpunkt der grünen mit der roten Linie steht für den Umfüllvorgang  (n,b) --> (0,b) .

Der Papiercomputer lässt in dieser Darstellung die Umfüllschritte klarer erkennen. Insbesondere wird sichtbar, dass die von der grünen Linie erreichten Punkte am oberen und am unteren Rand immer den Abstand  m  haben. Machen Sie sich das auch für andere Werte von  n  und  m  klar. Dies führt uns unmittelbar zu den nächsten Beweisschritten:


Aufgabe 5
Die bei den sukzessiven Umfüllschritten  -  beginnend bei (0,m)  -  erreichten Werte  a  in (a,0) und (a,m)  -  also die Füllmengen des großen Kruges, wenn der kleine Krug voll oder leer ist  -  sind zunächst die Vielfachen von  m  (verwenden Sie Aufgabe 3). Nach welcher Gesetzmäßigkeit geht es weiter, wenn dabei  n überschritten wird?  Tipp: Am einfachsten lässt sich dies mit der Modulo-Funktion ausdrücken.

Aufgabe 6
Mit der Folge der Füllmengen  a  aus Aufgabe 5 ist nun zu zeigen, dass auf dem Weg von (0,m) nach (n,0) alle Punkte am oberen und am unteren Rand des Papiercomputers genau einmal erreicht werden, mit Ausnahme von (0,0) und (n,m).  Damit ist dann bewiesen, dass alle (a,0) für  0 < a ≤ n  und alle (a,m) für  0 ≤ a < n  genau einmal erreicht werden.

Aufgabe 7
Aus Aufgabe 6 lässt sich leicht ermitteln, wieviele Kopien des Papiercomputers nebeneinander gelegt werden müssen, bis man das Ziel (n,0) erreicht hat. Damit können Sie zeigen: Auch alle Punkte am linken und am rechten Rand des Papiercomputers werden genau einmal erreicht, außer (0,0) und (n,m).  Damit ist dann bewiesen, dass alle (0,b) für  0 < b ≤ m  und alle (n,b) für  0 ≤ b < m  genau einmal erreicht werden. Man kann auch hier die Folge der erreichten Randpunkte mit Hilfe der Modulo-Funktion beschreiben und dann zusammenfassend die Abfolge der erreichten Füllstände beschreiben.  -  Zusammen mit Aufgabe 6 lässt sich jetzt noch zeigen: Für jedes  k < n  mit  k ≠ m  gibt es 2 oder 4 zugehörige Randpunkte.

Aufgabe 8
Die beiden Folgen der Umfüllschritte  -  beginnend bei (0,m) bzw. (n,0) -  sind lediglich in der Reihenfolge gespiegelt.

Aufgabe 9
Welche  k  werden erreicht, wenn  n  und  m  nicht teilerfremd sind?


Wir fassen zusammen:

Damit ist die Aufgabenstellung umfassend gelöst und die Idee von Y. I. Perelman gebührend gewürdigt.
Man sollte sich aber noch mit dem Fall befassen, dass in der Formulierung des Problems nicht ein Reservoir unbekannten Inhalts, sondern ein weiterer Krug mit Volumen  r ≥ n  vorkommt, der anfangs gefüllt ist. In vielen Aufgaben hat dieser Krug das Volumen  r = n + m ; z.B. ist das Beispiel mit Krügen von 3, 5 und 8 Litern Volumen sehr gängig. Manchmal sieht man auch  r > n + m . Diese beiden Fälle lassen sich bequem zusammenfassen, denn die bisher durchgeführten Beweisschritte lassen sich ohne weiteres auf  r ≥ n + m  anwenden, wenn man den größten Krug wie den Wasserbehälter behandelt. Allerdings lässt sich dann der Papiercomputer sinnvoll ergänzen: Neben jeden Randpunkt kann man den zugehörigen Füllungsstand des größten Kruges notieren und hat damit zusätzliche Möglichkeiten,  k  zu erreichen; insbesondere können sich dadurch kürzere Lösungswege ergeben. Außerdem kommen dann natürlich auch Werte  k > n  in Frage. In den nächsten beiden Aufgaben seien wieder n und m teilerfremd.

Aufgabe 10
Geben Sie je ein Beispiel für  r = n + m  und  r > n + m  an, in denen am Ende die abzumessende Menge  k  im größten Krug ist und man weniger Umfüllschritte benötigt als mit dem Verfahren aus (2). Man wird von Hand, d.h. mit dem Papiercomputer, recht schnell bei kleinen  n, m  fündig.

Aufgabe 11
Welche Mengen  k  kann man abmessen, wenn  r ≥ n + m  ist? In welchen Fällen kann man alle  k ≤ r  abmessen?


Der Fall  r > n + m  weist noch eine weitere interessante Facette auf: Das Ergebnis aus Aufgabe 9 stimmt hier nicht. Man kann in Einzelfällen bei nicht teilerfremden  n  und  m  Füllmengen  k  abmessen, die bei einem Reservoir unbekannten Inhalts nicht erreicht werden können.

Aufgabe 12
Sei  r > n + m  mit nicht teilerfremden  n  und  m .
Geben Sie ein Beispiel an, in dem jede Menge  k ≤ n  abgemessen werden kann.
Für welche  n, m, r  geht das im allgemeinen?
Warum kann man nie alle  k ≤ r  abmessen?



Und zum Schluss: Was ist mit  r < n + m ?  In diesem Falle wird der Papiercomputer an seiner oberen rechten Ecke "amputiert". Für  n = 5, m = 3, r = 6  sieht das so aus:



In diesem Beispiel lassen sich alle  k  erreichen. Aber gilt das immer?

r = n + m - 1  bedeutet keine Einschränkung; alle  k ≤ r  können abgemessen werden, denn es fehlt am Papiercomputer ja nur der Punkt (n,m), von dem wir gesehen haben, dass man ihn nicht benötigt.

Leider gilt das im Allgemeinen nicht für kleinere  r . Man kann das ausprobieren, indem man in unserem Eingangsbeispiel mit  n = 9  und  m = 7  einen dritten Krug mit Volumen  r = 12  einführt und versucht, die Menge  k = 6  abzumessen.

Lösung

Aufgabe 1

Wir zeigen ein Beispiel  ( n = 5, m = 3 ).



Man erkennt, dass im rechtwinkligen kartesischen Koordinatensystem die waagerechten Linien für die Füllung oder Leerung des großen Kruges stehen und die senkrechten für die Füllung oder Leerung des kleinen Kruges, jeweils mit Hilfe des Wasserbehälters. Die diagonalen Linien stehen für die Umfüllung vom großen in den kleinen Krug oder umgekehrt; man beachte, dass dabei die Gesamtmenge in den beiden Krügen konstant bleibt. Die Symmetrie wird gestört durch das Fehlen der Diagonalen in der anderen Richtung. Diese würden bedeuten, dass bei einem Umfüllschritt das Volumen in beiden Krügen anwächst, und das ist unmöglich. Diese Asymmetrie führt dazu, dass bei der Kippung der senkrechten Achse um 30° im Uhrzeigersinn in Perelmans Papiercomputer lauter gleichseitige Dreiecke entstehen. Natürlich könnte man auch mit einem rechtwinkligen Papiercomputer arbeiten, aber die Regel "Einfallswinkel = Ausfallswinkel" würde verlorengehen.


Aufgabe 2

Im ersten Schritt kann man nur einen der beiden Krüge füllen; dies führt also auf (n,0) oder (0,m). (Würde man einen Krug nur teilweise füllen, wüsste man nicht, wieviel er enthält.) Nun zum zweiten Schritt. Es ist sinnlos (auch in allen späteren Schritten), jetzt den anderen Krug ebenfalls zu füllen, denn von (n,m) kommt man nur wieder auf (n,0) oder (0,m) zurück. Es bleibt somit lediglich die Umfüllung von einem in den anderen Krug übrig. Die beiden ersten Schritte können also nur sein:

(0,0) --> (n,0) --> (n-m,m)
(0,0) --> (0,m) --> (m,0)

Wir vergleichen dies mit dem Papiercomputer. Die Diagonalen in \-Richtung bedeuten eine Umfüllung von einem Krug in den anderen. Also stimmt bis hierhin unsere Analyse mit der Benutzung des Papiercomputers überein, denn wir bewegen uns nur von Rand zu Rand nach der Regel "Einfallswinkel = Ausfallswinkel".

Wann endet das Verfahren? Es gibt die folgenden Abbruchkriterien:

-  Man erreicht (a,k) oder (k,b).
-  Man erreicht später als im 2. Schritt (n,0) oder (0,m), ohne eine Lösung gefunden zu haben.
-  Man erreicht einen Punkt (a,b) zum zweiten Mal, ohne eine Lösung gefunden zu haben.

Für diese Abbruchkriterien gilt, dass man beide möglichen Lösungspfade  -  über (n,0) oder (0,m)  -  jeweils bis zum Abbruch begehen sollte.

Man beachte: Man springt nie auf (0,0) oder (n,m), denn diese wären nur über (n,0) oder (0,m) zu erreichen.


Aufgabe 3

Der Induktionsanfang ergibt sich aus Aufgabe 2. Nach den ersten beiden Schritten ist entweder ein Krug leer oder ein Krug voll. Für alle weiteren Schritte (bis zum Erreichen des Abbruchkriteriums) ergeben sich dann die Möglichkeiten:

(a,0) --> (0,0)
      --> (n,0)
      --> (a,m)
      --> (a-m,m), falls a ≥ m
      --> (0,a), falls a ≤ m

(a,m) --> (0,m)
      --> (n,m)
      --> (a,0)
      --> (a+m,0), falls a ≤ n-m
      --> (n,m-n+a), falls a ≥ n-m

(0,b) --> (0,0)
      --> (0,m)
      --> (n,b)
      --> (b,0)

(n,b) --> (n,0)
      --> (n,m)
      --> (0,b)
      --> (n-m+b,m)


Anhand dieser Aufstellung überzeugt man sich, dass alle Umfüllschritte rückgängig gemacht werden können.

Zurück zu Induktion: Nach den ersten beiden Umfüllschritten hat man also immer vier Möglichkeiten für den nächsten Schritt (bis zum Erreichen des Abbruchkriteriums). Alle vier führen wieder auf einen "Randpunkt" (a,0), (a,m), (0,b) oder (n,b), also ist auch nach dem Umfüllen wieder ein Krug leer oder voll. Von den vieren kommt aber nur eine in Frage. Denn zwei führen auf einen "trivialen Füllstand" (0,0), (n,0), (0,m) oder (n,m), die es zu vermeiden gilt, solange man noch andere Möglichkeiten hat. Von den beiden anderen Möglichkeiten (fett dargestellt in der Liste oben) ist eine die Umkehrung des vorherigen Schrittes und scheidet ebenfalls aus. Somit ist jeder Schritt eindeutig bestimmt.

Die beiden ersten Behauptungen aus dieser Aufgabe sind nun induktiv gezeigt. Die letzte Behauptung ist trivial: Wenn man mit einem der oben aufgelisteten sinnvollen Umfüllschritte auf (0,m) oder (n,0) läuft, ist dies bereits der letzte Schritt (Abbruchkriterium).

Die jeweils vier Möglichkeiten des Umfüllens entsprechen im Papiercomputer den vier Richtungen, in die man von einem Randpunkt aus laufen kann, sofern er kein Eckpunkt ist.

Die strikte Analogie zwischen den oben formalisierten Umfüllschritten und dem Papiercomputer wird erzeugt, indem man nachprüft, dass sich jeder Umfüllschritt beschreiben lässt mit den in der Problemstellung eingeführten Kürzeln G/K "füllen", "leeren", "umfüllen", z.B.

(n,b) --> (n-m+b,m)      G nach K umfüllen

Im Papiercomputer gibt es nur die Richtungen " - ", " / " und " \ " mit den Bedeutungen:
-   G leeren/füllen
/   K leeren/füllen
\   umfüllen von K nach G oder umgekehrt

Dies harmoniert mit den formalen Schritten in der Liste oben. Schließlich ist noch leicht nachzuprüfen, dass alle sinnvollen Umfüllschritte der Regel "Einfallswinkel = Ausfallswinkel" genügen.

Wie lässt sich eine einfache Anweisung zum Umfüllproblem formulieren, wenn der Papiercomputer nicht zur Hand ist? Das ist nach unseren Untersuchungen nun nicht mehr schwer:

-  Erster Schritt: Fülle einen der beiden Krüge.
-  Vermeide in allen folgenden Schritten die Umkehrung des jeweils
      vorigen Schrittes und (solange es geht) die trivialen Füllstände.
-  Man erreicht entweder sein Ziel (a,k) bzw. (k,b) oder muss feststellen,
      dass dies nicht erreichbar ist (nämlich wenn man auf (n,0) oder (0,m) läuft).

Wo ist das letzte Abbruchkriterium aus Aufgabe 2 geblieben? Wir werden in den folgenden Aufgaben noch zeigen, dass kein Füllstand der Krüge mehr als einmal erreicht werden kann.


Aufgabe 4

Sei  t > 1  ein gemeinsamer Teiler von  n  und  m . (a,b) sei irgendein Füllstand, der nach dem Verfahren aus den Aufgaben 2 und 3 zustandekommt. Nach Aufgabe 2 sind dann nach dem ersten und zweiten Umfüllschritt  a  und  b  durch  t  teilbar. Aus der Auflistung der Umfüllschritte in Aufgabe 3 folgt induktiv, dass sich die Teilbarkeit der Kruginhalte durch  t  im weiteren Verlauf nicht verändert.

Also lassen sich höchstens solche Mengen  k  abmessen, die durch  t  teilbar sind.


Aufgabe 5

Ein  k  als Ziel ist hier nicht vorgegeben, sondern die Umfüllschritte sollen bis zum Erreichen des Abbruchkriteriums weitergeführt werden.

Nach Aufgabe 3 geht es so los:

(0,0) --> (0,m) --> (m,0) --> (m,m) --> (2m,0) --> (2m,m) --> (3m,0) --> ... ,

allerdings nur so lange, wie  i·m < n . Nach Aufgabe 3 geht es dann so weiter:

(*)   (i·m,m) --> (n,(i+1)·m - n) --> (0,(i+1)·m - n) --> ((i+1)·m - n,0)

Wir erkennen, dass sich nun in der ersten Komponente die Vielfachen von  m  fortsetzen, allerdings reduziert um  n . Dieser Effekt war aufgrund der Idee mit den aneinandergelegten Papiercomputern zu erwarten, und er führt auf die Vermutung:

Beachtet man in der Abfolge der Füllstände (a,b) nur diejenigen mit  b = 0  und  b = m , so erhält man
(i·m mod n,0), (i·m mod n,m)     i = 0,1,2,...

Noch genauer ist diese Vermutung dargestellt im folgenden Bild.


i₁m ... i₂m  sollen dabei aufeinanderfolgende Vielfache von  m  sein.
* steht als Abkürzung für  mod n .
Die gestrichelte Linie weist auf die iterative Wiederholung hin.

Das dies der tatsächliche Ablauf ist, ergibt sich induktiv. Der Einstieg am linken Rand des Bildes entspricht dem Anfang des Beweises mit  i₁ = 1 . Beim ersten Durchlauf entspricht der rechte Teil des Bildes der Abfolge (*) mit  i = i₂ . Die weiteren Schritte folgen dann direkt aus Aufgabe 3, nach der es immer eine eindeutige Fortsetzung gibt, wenn der vorige Umfüllschritt bekannt ist. Die Iteration endet, wenn (i₂+1)m mod n = 0 , also bei (n,0).


Aufgabe 6

Wir müssen nur zeigen, dass  { j·m mod n | j = 0 ... n-1 } = { 0, ..., n-1 } , d.h. für  j₁ > j₂  ist  j₁·m mod n ≠ j₂·m mod n . Dies ist ein bekannter Satz der Zahlentheorie und folgt aus der Teilerfremdheit von  n  und  m :

Aus  j₁·m mod n = j₂·m mod n  (o.E.  j₁ ≥ j₂ ) würde folgen, dass  (j₁-j₂)·m  ein Vielfaches von  n  ist. Aber  kgV{n,m} = n·m , und  j₁-j₂ < n . Also folgt  j₁ = j₂ .

Soll also eine Menge  k < n  abgemessen werden, ist dies immer möglich, und zwar im großen Krug, und auf zwei Weisen (kleiner Krug leer oder voll). Denn zusammen mit Aufgabe 5 haben wir soeben nachgewiesen, dass alle Randpunkte (k,0) und (k,m) für  k = 0 ... n-1  genau einmal erreicht werden. Der Punkt (n,0) kommt noch hinzu, und zwar am Ende der Iteration in Aufgabe 5.


Aufgabe 7

Wir betrachten den unteren Rand der aneinandergelegten Papiercomputer. Der Abstand der erreichten Punkte beträgt jeweils  m ; dies ist wegen Aufgabe 5 lediglich für die "Nahtstellen" zu zeigen:
Nach Aufgabe 5 (Graphik) muss der Sprung von (i₂m*,0) nach ((i₂+1)m*,0) betrachtet werden, also (n-i₂m*)+(i₂+1)m* , so wie im folgenden Bild:



Setzt man in der Lösung von Aufgabe 3 (a,b)=(i₂m*,0) , so ist die weitere Abfolge:

(a,0) --> (a,m) --> (n,m-n+a) --> (0,m-n+a) --> (m-n+a,0)

Daraus folgt mit Aufgabe 5: (i₂+1)m* = m-n+a = m-n+i₂m* . Somit ist (n-i₂m*)+(i₂+1)m* = m .

Es gibt also am unteren Rand  n+1  erreichte Punkte (Aufgabe 6) im Abstand  m  (incl. (0,0) und (n,0)). Man legt deshalb  m  Papiercomputer nebeneinander und erhält eine Zickzacklinie von (0,m) nach (n,0).

Nun betrachten wir den linken und den rechten Rand des Papiercomputers; formal: (0,b) und (n,b). Ingesamt (m-1)-mal überquert der "Lösungspfad" diese Nahtstellen. Würden dabei nicht alle  b  zwischen  1  und  m-1  durchlaufen, würde eines dieser  b  ein zweites Mal erreicht; damit würde der Lösungspfad in einen geschlossenen Kreislauf einmünden und (n,0) nie erreichen. Da dies im Widerspruch zu den bisherigen Beweisen steht, werden alle Punkte am linken und am rechten Rand außer den Eckpunkten genau einmal erreicht.

Die Abfolge der zugehörigen Koordinaten  b  ist ähnlich wie die der Koordinaten  a  am oberen bzw. unteren Rand. Dafür bedient man sich am besten eines kleines Tricks. Denn die Argumentation für die Aufgaben 5 und 6 lässt sich ganz analog für übereinander gelegte Papiercomputer durchführen. Dann bilden die oberen und unteren Ränder die Nahtstellen, und man erhält wieder eine Zickzacklinie als Lösungspfad. Die Analogie erfordert dann allerdings einen Start bei  (n,0) , und entlang des linken und des rechten Randes werden alle Vielfachen von  n mod m  durchlaufen.

Die Füllstände des großen und des kleinen Kruges "treffen sich" an den Nahtstellen der nebeneinandergelegten Papiercomputer (siehe Lösungen Aufgaben 3 und 5). Dies ermöglicht eine sehr schöne Beschreibung der durchlaufenen Füllstände: Man notiert alle Vielfachen von  m  (modulo n) in eine Zeile und darunter alle Vielfachen von  n  (modulo m) in umgekehrter Reihenfolge. Dabei schreibt man gleiche Zahlen etwas versetzt übereinander, so wie in den folgenden Beispielen.

n = 5 ,  m = 3
3 1 4 2
 1   2

n = 9 ,  m = 7
7 5 3 1 8 6 4 2
 5 3 1   6 4 2

Die obere Zeile steht für die Füllstände des großen Krugs G, die untere für die Füllstände des kleinen Krugs K. Jede Zahl in der oberen Zeile muss zweimal gelesen werden, zuerst für K leer, dann für K voll. Jede Zahl in der unteren Zeile muss zweimal gelesen werden, zuerst für G voll, dann für G leer. Nochmal ausführlich für das erste Beispiel:

(3,0) (3,3) (5,1) (0,1) (1,0) (1,3) (4,0) (4,3) (5,2) (0,2) (2,0) (2,3)

Damit hat man die gesamte Abfolge zwischen (0,3) und (5,0), die sich natürlich auch rückwärts lesen lässt.

Und zum Schluss:  k = m  und  k = n  sind uninteressant, da sie mit einer Krugfüllung erreicht werden können. Da alle nicht-trivialen Randpunkte genau einmal erreicht werden, kommt jedes  k < m  viermal und jedes  k < n  mit  k > m  zweimal am Rand des Papiercomputers vor.


Aufgabe 8

Es gibt einen eindeutigen Weg von (0,m) nach (n,0) und einen eindeutigen Weg von (n,0) nach (0,m), alle Schritte sind umkehrbar. Nach der Lösung zu Aufgabe 3 ist der letzte Schritt des ersten Weges der Anfangsschritt des zweiten Weges (natürlich in umgekehrter Richtung). Somit sind die beiden möglichen Lösungspfade Umkehrungen voneinander.


Aufgabe 9

In Aufgabe 4 hatten wir schon erkannt, dass man höchstens die Vielfachen von  g = ggT{n,m} abmessen kann. Nun wird gezeigt, dass diese auch wirklich erreicht werden können. Man muss nur eine neue Einheit einführen, nämlich  1 "Neuliter" = g Liter. Dann fassen die beiden Krüge  n₁ = n/g  bzw.  m₁ = m/g Neuliter;  n₁ und  m₁ sind teilerfremd, also lassen sich beliebige  k ≤ n₁ Neuliter abmessen.


Aufgabe 10

n = 5 ,  m = 2 ,  r = 7 ,  k = 4
n = 5 ,  m = 3 ,  r = 9 ,  k = 4


Aufgabe 11

k = 1 ... n  lassen sich mit der ursprünglichen Version des Papiercomputers abmessen. Trägt man am Rand des Papiercomputers bei (a,b) den jeweiligen Füllungsstand des größten Kruges ein, so findet man damit  k = r-a-b . Nun lässt man (a,b) alle Randpunkte durchlaufen und erhält  k = r-n-m ... r .

Man kann  k = 1 ... n  und  k = r-n-m ... r  abmessen, wobei sich die beiden Bereiche überlappen können. Ist  k = r-n-m > n , so muss zur Abmessung von  k  ausnahmsweise der Füllstand (a,b)=(n,m) hergestellt werden (geht in zwei Schritten).

Die beiden Bereiche für  k  ergeben vereinigt alle natürlichen Zahlen bis  r , wenn  n ≥ r-n-m-1 .



Aufgabe 12

Ist  n = 4, m = 2, r = 7 , so lassen sich im größten Krug  k = 1  (für (a,b)=(4,2)) und  k = 3  (für (a,b)=(2,2)) abmessen.

Dieses Beispiel legt die Verallgemeinerung auf  n  gerade,  m = 2  und  r = n+3  nahe. Am oberen Rand des Papiercomputers erreichen wir außer den geraden  k  im großen Krug zusätzlich die ungeraden  k = r-m, r-m-2 ... r-m-n , also  k = n+1 ... 1  (absteigend in 2er-Schritten) im größten Krug.

Es lassen sich für  r > n + m  nie alle  k ≤ r  abmessen, denn  k = r-1  im größten Krug bedeutet (a,b)=(1,0) oder (a,b)=(0,1); aber  1 < ggT{n,m} .

Publiziert 2008-10-05          Stand 2007-09-07

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem