---

Lösung der 8.    vom 30.04.2001

---

Vorbemerkung: Wir gehen davon aus, dass der Schachspieler leere "Felder" nicht noch einmal leer essen kann.

das Prinzip des Rösselsprungs anhand der Grafiken von Johann Moll:

3x4:

4x5:

5x5:

Heinz Mayr ist systematisch alle möglichen Brettgrößen durchgegangen:


Es handelt sich um eine Variante des altbekannten "Springerproblems", das schon Euler
untersucht hat: Ein Springer soll alle Felder des Schachbretts durchlaufen,
wobei er jedes Feld genau einmal besucht.
Anstelle des normalen Schachbretts kann man natürlich jedes rechteckige bzw.
quadratische Brett der Form m*n betrachten. Im folgenden gebe ich eine kurze
Übersicht über die Lösungsmöglichkeiten. Die Bilder sollen jeweils den Weg des
Springers darstellen, wobei das Startfeld "1" ist.

Brettgröße m*n mit m<=n

m=1 oder m=2 : unmöglich, sofern man den Trivialfall 1*1 ausschließt.

m=3 : 

3*3 unmöglich, da das Zentralfeld vom Rand aus nie erreicht wird

3*4 mögliche Lösung:

 

3	6	11	8
12	9	2	5
1	4	7	10

Dies ist also das kleinste Brett, für das eine Lösung existiert !

3*5 keine Lösung !

3*6 keine Lösung !

Eine "kurze Begründung" dafür gibt es nicht - es bleibt nichts anderes übrig
als alle Möglichkeiten durchzuspielen (s.u.)

3*7 mögliche Lösung:

13	2	15	18	9	4	7
16	19	12	3	6	21	10
1	14	17	20	11	8	5

Alle Bretter der Größe 3*n für n>=7 lassen eine Lösung zu !

m=4: 

4*4 nicht lösbar

4*5 mögliche Lösung :

1	12	5	18	9
6	17	10	13	4
11	2	15	8	19
16	7	20	3	14

Alle Bretter der Größe 4*n mit n>4 sind lösbar !

Für alle übrigen Bretter m*n mit m,n >= 5 gibt es immer Lösungen !

Das kleinstmögliche quadratische Brett ist also 5*5 !

1	10	21	16	7
20	15	8	11	22
9	2	23	6	17
14	19	4	25	12
3	24	13	18	5

In der Literatur und im Internet findet man eine ganze Reihe von Programmen,
mit denen man den Wege des Springers ermittelt. Bei umständlicher Programmierung,
z.B. mit dem "Backtracing"-Verfahren, kann das ganz schön lange dauern, raffinierte
Programme schaffen auch sehr große Bretter in Sekunden.

auch eine sehr anschauliche und ausführliche Lösung  schickte Oliver Gronau:

Du kannst Dir gar nicht vorstellen, wie groß die Bauchschmerzen waren, nachdem ich den Versuch mit den Toffifee selber nachvollzogen habe ;-)

Jetzt aber ernsthaft:
Zu den Fragen die Du gestellt hast, lassen sich folgende Antworten geben:
4x5 Brett: möglich
3x5 Brett: unmöglich
Kleinste Rechteck: 3x4
Kleinste Quadrat: 5x5

Zu den ersten beiden Fragen reicht ein Beispiel, bzw. ein Gegenbeweis:

Zuerst das 4x5 Brett:

Zugfolge:


Gegenbeweis zum 3x5 Brett:



Wenn o.B.d.A diese Färbung vorliegt, sind mehr weiße als schwarze Felder vorhanden. D.h. eine Tour muss auf einem weißen Feld beginnen, und auch auf einem solchen
enden. Schwarze Felder sind also allesamt "innere" Felder, von denen jedes betreten und auch wieder verlassen werden muss.
Die beiden markierten Felder sind aber jeweils nur über die zwei mittleren Randfelder zu erreichen, und daher müsste an dieser Stelle ein "Kreis" vorliegen, was aber unmöglich ist.
q.e.d.


Zu den kleinsten Brettern:

Zuerst einmal sind Seitenlängen größer als 2 notwendig, da man sich auf solchen 2 x n Brettern nur "vorwärts" in einer Richtung bewegen könnte.

Das 3x3 Feld scheidet wegen des mittleren Feldes aus:



Da man auf einem 3x4 Feld eine Tour findet, muss dies das kleinste Rechteck sein:

Die Sache mit den Quadraten liegt komplizierter.

Zu 4x4 fällt mir kein einfacher Gegenbeweis wie oben ein, aber wenn man einige Überlegungen investiert (hier ausgelassen, ich liefere sie Dir aber gerne nach), kann man
ohne die Allgemeinheit zu beschränken folgende notwendige Grundstruktur einer Zugfolge finden (d.h. gestartet und geendet wird in zwei benachbarten Ecken und zwei
innen nebeneinanderliegende Felder hätten die Nummern 4 und 13):

Nun ist es aber jetzt unmöglich von 4 nach 13 zu kommen, denn ist man von der 4 auf eines der zwei möglichen Felder gesprungen, so kann man nur noch auf die Felder
gleicher Punktfarbe kommen, da ein Wechsel zwischen Rot und Grün unmöglich ist.

Zu dem 5x5 Brett möchte ich letztlich und schlussendlich nur noch ein aus dem Netz kopiertes ;-) Bild zeigen, da ein existierender Weg ja ausreicht.

Roland Koppenberger gibt für die "rösselsprung gerechten Verpackungen" immer noch die Anzahl der Möglichkeiten mit an:

Ich denke, dass für dein süßes Beispiel der Schweizer Leonhard Euler Pate gestanden hat, wobei er noch nicht wusste, dass er damals auf Hamiltonschen Wegen lustwandelte…

Der Inhalt einer 4x5-Packung mit 20 Stück Leckereien lässt sich korrekt springerproblematisch verzehren, man verfahre etwa in nachstehender Reihenfolge:

Insgesamt könnte man die 4x5-Packung auf 164 verschiedene angabenkonforme Arten konsumieren, symmetrische Vorgangsweisen eingeschlossen.


Kleinstmögliche rechteckige Verpackungsform
Die minimalste potentielle Form ist die 2x3-Schachtel, die aber (wie ihre Verlängerung bis zu 2xN) offensichtlich nicht zum springerproblematischen Konsum aller Naschereien führt. Die nächstkleinere (und zugleich kleinstmögliche) rechteckige Form ist die 3x4-Schachtel. Eine der (teilweise symmetrischen) 16 Möglichkeiten ist etwa:

Kleinstmögliche quadratische Verpackungsform
ist die 5x5-Schachtel. Ein ästhetisches Beispiel für die 5x5-Form (ästhetisch insofern, als jeweils die Summe der Reihenfolgenummern zweier mittelpunktsymmetrischer Felder genau immer die ursprüngliche Anzahl an Naschereien erhöht um eins ergibt):

Insgesamt könnte man die 5x5-Packung auf 1728 verschiedene angabenkonforme Arten konsumieren, symmetrische Vorgangsweisen eingeschlossen.

Von Stefan zum Schluss noch ein Applet zum bestimmen der Verteilung der Züge

Applet

Auswertung:

 [ aktuelle Aufgabe ]  [ zur 8. zurück ]  [ zur Hall of FAME ] 

?     ?        ?    ?