Rätsel und Puzzles
Los Acertijos de Oscar Nr. 1
Eine Ameise beginnt ihre Reise, die sie genau ein mal durch alle Felder des Diagramms führt, auf Feld 13. Jede Etappe führt sie zu einem beliebigen Feld, das sie noch nicht besucht hat. Die Distanz zu diesem Feld berechnet sich zu Δ=Δx+Δy, z.B.
13 -> 10: Δx(3) + Δy(0) = 3 13 -> 2: Δx(1) + Δy(2) = 3 2 -> 24: Δx(2) + Δy(4) = 6
Finden Sie einen möglichst langen Weg!
Wir legen ein Koordinatensystem auf die Felder, so dass jedes Feld ganzzahlige Koordinaten hat. Das Mittelfeld 13 soll (0,0) haben, das Feld 1 (0,3), ...
Zuerst betrachten wir geschlossene Wege, die Ameise kehrt also an den Ausgangspunkt zurück.
Außerdem betrachten wir zuerst nur die x-Koordinate. Bei einem geschlossenen Weg tritt jedes Feld 2-mal auf, als Anfangspunkt und Endpunkt eines Wegstückes. Die Koordinaten der Punkte seien (in der Reihenfolge des Weges) x1, x2, ..., x25. Damit ist die Weglänge (nur die x-Werte!)
l = abs(x1 - x2) + abs(x2 - x3) + ... + abs(x24 - x25) + abs(x25 - x1)
(abs sei der Absolutbetrag)
Wegen der Definition des Betrages ist abs(x - y) = x - y falls x>=y oder abs(x - y) = y - x falls x<y.
Damit ergibt sich bei l, dass 25 Zahlen addiert werden und davon 25 Zahlen subtrahiert werden. Es treten auf: 2-mal -3, 6-mal -2, 10-mal -1, 14-mal 0, 10-mal 1, 6-mal 2 und 2-mal 3. Damit kann l maximal 56 werden, dazu müssen die 18 positiven Zahlen addiert werden, die 18 negativen Zahlen müssen subtrahiert werden und die Nullen werden je 7-mal addiert bzw. subtrahiert.
Dieselbe Überlegung gilt auch für die y-Werte. Da die Weglänge der Aufgabe aus den Differenzen der x-Werte und y-Werte besteht, ergibt sich eine (theoretische) maximale Weglänge von 112.
Da die Ameise nicht zurückkehrt, muss man ein möglichst kleines Wegstück weglassen (1), also ist das Maximum theoretisch 111.
Wenn man einen Weg findet, der die Länge 111 hat, ist also bewiesen, dass die maximal Weglänge 111 ist.
Ein solcher ist z. B.:
13, 10, 1, 16, 25, 2, 24, 5, 21, 6, 15, 22, 3, 20, 11, 4, 23, 9, 17, 8, 18, 7, 14, 19, 12.
Die maximale Weglänge beträgt 111. (Wenn man am Schluss wieder zum Feld 13 zurück wollte, wären es 112.)
Es gibt viele mögliche Lösungen, wobei es nur auf zwei Dinge ankommt:
Quadrant I (rechts oben): 1, 3, 4, 7, 8, 9, 13, 14, 15, 16
Quadrant II (links oben): 1, 2, 3, 5, 6, 7, 10, 11, 12, 13
Quadrant III (links unten): 10, 11, 12, 13, 17, 18, 19, 22, 23, 25
Quadrant IV (rechts unten): 13, 14, 15, 16, 19, 20, 21, 23, 24, 25
Man springt also immer von I nach III (oder zurück) oder von II nach IV (oder zurück).
Um alle vier Quadranten zu erreichen, muss man natürlich mindestens einmal das Quadrantenpaar wechseln (also z.B. zuerst I<->III, dann II<->IV). Dazu benutzt man die Felder auf der waagrechten und der senkrechten Achse (10, 11, 12, 14, 15, 16, 1, 3, 7, 19, 23, 25), da diese jeweils zu zwei Quadranten gehören. Ein Beispiel für so einen "Diagonalenwechsel" wäre:
... -> 9 -> 18 -> 7 -> 24 -> 2 -> ...
Zwei Lösungen, die diese Bedingungen erfüllen, wären beispielsweise:
13, 9, 25, 8, 17, 3, 23, 4, 22, 15, 18, 7, 10, 1, 19, 5, 21, 6, 16, 2, 20, 12, 24, 11, 14
und schön spiralförmig:
13, 1, 25, 4, 22, 9, 17, 16, 10, 21, 5, 24, 2, 23, 3, 18, 8, 11, 15, 6, 20, 7, 19, 14, 12
Der mathematische Beweis dazu ist ziemlich einfach, aber ich bin zu faul, ihn aufzuschreiben. :-) Die Formel lautet jedenfalls:
Maximale Weglänge = 8*(12+22+32) - 1 = 111
Man könnte das Diagramm auch größer oder kleiner machen. Im vorliegenden Fall hat jedes Feld maximal Abstand 3 (berechnet als Δ=Δx+Δy) vom Mittelpunkt. Würde man Abstand n nehmen, wäre die Formel
8*(12+22+...+n2) - 1
(das kann man dann auch noch umwandeln in 4/3*n*(n+1)*(2n+1) - 1, aber da wird's langweilig.)
... und was wäre die Formel, wenn es sich statt um ein zweidimensionales Diagramm um einen dreidimensionalen Würfel handeln würde? Und wäre die Ameise dann eine Termite?