Lösung zu Aufgabe 21

[Fanbusfahrer]

Die richtige Lösung ist 2, also 33.
Eine solche Lösung zu finden, geht recht schnell.
Wir färben die Felder abwechseln schwarz und weiß.
Nun erkennen wir, dass durch die Weise des Springens immer Dominosteine entstehen, die sozusagen eine weiße und eine schwarze Seite haben. Insgesamt gibt es 35 Felder, wovon 17 weiß und 18 schwarz sind (das Anfangs-und das Endfeld zählen jeweils einzeln als ein Feld). Es muss damit mindestens ein weißes Feld leer bleiben.
Das Prinzip dahinter ist das Färbungsprinzip. Wirklich eine elegante, coole Aufgabe.

[Martina]

Die genannte Lösung kaufe ich leider so nicht, und ich kann sie auch nicht so recht nachvollziehen. Das Färbungsprinzip allein hilft hier nicht, und ich halte die genannte Lösung auch weder für richtig noch für ausreichend begründet, denn mit Dominosteinen kann man das gesamte Feld überdecken, da jede Farbe genau 17mal vorkommt. 

Ich präsentiere hier mal meine Lösung:

Anhand des Beispiels in der Aufgabenstellung sieht man, dass die Anzahl der geprüften Quadrate zählt, dh, auch wenn sie ihr Startfeld zweimal betritt, zählt das als ein Quadrat. Im Beispiel prüft sie 6 Quadrate. Wenn man das Färbungsprinzip zugrunde legt, sieht man, dass sich die Feldfarbe nach jedem Schritt ändert (siehe auch weiter unten). Daher muss die Zahl der geprüften Quadrate auf jeden Fall gerade sein!

Wir nummerieren die Felder durch von rechts nach links und von oben nach unten. Dh oberste Reihe Felder A1-A9, zweite Reihe Felder B1-B9 (Nummer B5 ist kaputt), dritte Reihe C1-C9 (Nummer C5 ist kaputt), unterste Reihe Felder D1-D9.

Zuerst zeigen wir, dass sie maximal 32 Felder ablaufen kann. Dafür färben wir nach dem bekannten Muster die Felder immer abwechselnd schwarz-weiß und sehen: Wir bekommen 17 schwarze und 17 weiße. Sie läuft zunächst einen langen Schritt (Springer-Zug) und dann einen einzelnen Schritt auf ein benachbartes Feld, dh, bei jedem Schritt ändert sich die Feldfarbe. Theoretisch könnte sie also alle 34 Felder ablaufen. Warum sind es trotzdem nur 32?

Schauen wir uns an, wie der Springer-Zug funktioniert: Man geht einen Schritt auf ein benachbartes Feld, dann einen Schritt diagonal, so dass man nicht auf einem benachbarten Feld landet. In unserem Falle heißt das: Egal, von wo aus man losläuft, die Felder in den Reihen B und C sind zwingend am Springer-Zug beteiligt. Entweder startet man von da aus oder man landet dort. Da es in diesen beiden Reihen aber nur noch 16 begehbare Felder gibt, kann es maximal 16 Doppelschritte (langer Schritt plus kurzer Schritt) geben, also insgesamt 32 Quadrate, die geprüft werden (nochmals: Das Anfangsfeld wird zwar zweimal betreten, zählt aber nur als ein abgelaufenes Quadrat).

Jetzt zeigen wir eine Lösung, wo die 32 Quadrate auch tatsächlich abgelaufen werden:

Wir starten oben in der Mitte auf Feld A5, dann geht eine mögliche Feldfolge so:

A5 - A4 - B2 - B1 - A3 - B3 - A1 - A2 - B4 - (alle Felder des oberen linken 2x4-Rechtecks abgelaufen, da unser nächster Schritt ein kleiner ist, spiegeln wir das jetzt
C4 - D2 - D1 - C3 - D3 - C1 - C2 - D4 - D5 - (alle Felder des linken 4x4-Quadrates abgelaufen plus die Felder oberhalb und unterhalb der Bruchstelle)
C7 - C6 - D8 - C8 - D6 - D7 - C9 - (untere Hälfte des rechten 4x4-Quadrates durch, wieder haben wir einen kleinen Schritt vor uns, deshalb spiegeln wir jetzt wieder)
B9 - A7 - A6 - B8 - A8 - B6 - B7 und dann wieder zurück auf A5.

Macht 32 betretene Quadrate. Die richtige Lösung ist meiner Ansicht nach also 3.

Dieser Beitrag wurde zuletzt bearbeitet: 01-01-2024, 10:24 AM von Martina. Bearbeitungsgrund: Klarifizierung

[Stella]

Ich bin auch nur auf 32 gekommen…

[Fanbusfahrer]

Oh shit.
Ich kam in meinem Beispiel auch nur auf 32, was mir jetzt erst aufgefallen ist. Mist.
Ich hatte auch erst 32 angeklickt, dann aber keinen Beweis gefunden. Und dann ist mir das mit dem Färbungsprinzip eingefallen. Mir hat dein Argument gefehlt:

PHP-Code:

Wenn man das Färbungsprinzip zugrunde legt, sieht man, dass sich die Feldfarbe nach jedem Schritt ändert (siehe auch weiter unten). Daher muss die Zahl der geprüften Quadrate auf jeden Fall gerade sein! 


Damit hätte ich die Höchstzahl 32 begründen können.
Vielen Dank dafür.

---

Passt das so?


Insgesamt gibt es mit dem Endfeld 35 Felder, wovon 17 weiß und 18 schwarz sind. Da immer von weiß nach schwarz gesprungen wird, muss ein Doppelfeld leer bleiben. Maximal möglich sind damit 33 Felder. Da allerdings ein Sprung immer von einem weißen auf ein schwarzes Feld erfolgt, muss die Maximalzahl gerade sein. Damit ist 32 die Höchstgrenze.

Dieser Beitrag wurde zuletzt bearbeitet: 01-01-2024, 12:52 PM von Fanbusfahrer.

[Martina]

---

Passt das so?


Insgesamt gibt es mit dem Endfeld 35 Felder, wovon 17 weiß und 18 schwarz sind. Da immer von weiß nach schwarz gesprungen wird, muss ein Doppelfeld leer bleiben. Maximal möglich sind damit 33 Felder. Da allerdings ein Sprung immer von einem weißen auf ein schwarzes Feld erfolgt, muss die Maximalzahl gerade sein. Damit ist 32 die Höchstgrenze.

Nein, das reicht leider nicht, da nicht klar ist, dass immer von weiß nach schwarz gesprungen wird. Man könnte genauso auch von schwarz nach weiß springen. Es steht der Elfe frei, zuerst einen Sprung zu machen oder einen Schritt auf ein Nachbarfeld. Außerdem darf sie anfangen, wo sie will.

[Fanbusfahrer]

Ja. Das dürfte aber in der Argumentation drin sein. Hier nochmal anders:

Insgesamt gibt es mit dem Endfeld 35 Felder, wovon 17 weiß und 18 schwarz gefärbt werden von mir. Da immer von weiß nach schwarz oder von schwarz nach weiß gesprungen wird, muss ein Doppelfeld leer bleiben. Maximal möglich sind damit 33 Felder. Da allerdings ein Sprung immer von einem weißen auf ein schwarzes Feld oder von einem schwarzen auf ein weißes erfolgt, muss die Maximalzahl gerade sein. Damit ist 32 die Höchstgrenze.

Oder passt der erste Gedanke komplett nicht?

[marac]

Ja. Das dürfte aber in der Argumentation drin sein. Hier  nochmal anders:

Insgesamt gibt es mit dem Endfeld 35 Felder, wovon 17 weiß und 18 schwarz gefärbt werden von mir. Da immer von weiß nach schwarz oder von schwarz nach weiß gesprungen wird, muss ein Doppelfeld leer bleiben. Maximal möglich sind damit 33 Felder. Da allerdings ein Sprung immer von einem weißen auf ein schwarzes Feld oder von einem schwarzen auf ein weißes erfolgt, muss die Maximalzahl gerade sein. Damit ist 32 die Höchstgrenze.

Oder passt der erste Gedanke komplett nicht?

Nee, wenn du von den real vorhandenen 34 Feldern, die brav 17/17 gefärbt sind, eines doppelt nimmst (dein Startfeld), dann ist das kein Argument dafür, dass dann ein Doppelfeld ausscheiden muss, weil man ja gleich viele weiße und schwarze Felder betreten muss...

Die Färberei hilft in diesem Fall tatsächlich nur dazu, schon mal sicher zu sagen, dass man eine gerade Anzahl Felder betreten muss, um vom letzten aus wieder zum ersten springen zu können.

Dass nicht alle 34 Felder betreten werden können, hatte ich tatsächlich nur durch mehrfaches Ausprobieren erahnt, aber Martina hat dafür ja eine überzeugende Erklärung geliefert (jeder Rösselsprung startet oder endet auf einem Feld der mittleren beiden Zeilen, da in diesen beiden Zeilen aber nur insgesamt 16 Felder zur Verfügung stehen, kann es insgesamt nicht mehr als 32 Züge geben, wenn jeder zweite ein Rösselsprung ist.

[Mathe Juergen]

Ich habe ein ähnliches Prinzip wie Martina angewandt:

Schritt 1: Da sich bei jedem Schritt die "Farbe" ändern muss, kann man nur mit einer geraden Anzahl von Schritten wieder auf das Ursprungsfeld (Ursprungsfarbe) gelangen.

Schritt 2: Nicht jede gerade Anzahl ist möglich.
              Ich führe ein Koordinatensystem für unser "Schachbrett" ein. Es gibt also eine x und eine y- Koordinaten. Diese Koordinaten können durch die beiden Sprünge wie folgt verändert werden. 

              Pferdsprung: Delta x (kurz dx)  entweder  dx = ± 1 und dy = ± 2    oder  dx = ± 2 und dy = ± 1

              kurzer Sprung: entweder  dx = ± 1 und dy = 0    oder  dx = 0 und dy = ± 1

              Führt man also ein Sprungpaar (Reihenfolge ist egal) aus, dann gibt es folgende Möglichkeiten:  

              Fall 1:   dx = 0 ; ± 2  und  dy = ± 2  

              Fall 2:   dx = ± 1   und  dy = ± 1 ; ± 3 

              Fall 3:   dx =± 1 ; ± 3 und  dy = ± 1  

              Fall 4:  dx = ± 2  und  dy = 0; ± 2 

              Man beachte die "Symmetrie" der Fälle. Zudem gibt es natürlich auch Änderungen, die sowohl in Fall 1 und auch in Fall 4  bzw. sowohl in Fall 2 als auch in Fall 3 enthalten sind.

              Nach einem Sprungpaare "landet" man also immer auf einem anderen Feld, egal auf welchem Feld man vor dem Sprungpaar stand.

              Nennen wir die Sprungpaare in den Fällen 1 und 4 "gerade" (kurz: g) und in den Fällen 2 und 3 "ungerade" (kurz: u).

              Sei n die Anzahl der Sprünge ==> n = 2*k , wobei k ∈ N die Anzahl der Sprungpaare ist. 

              Wenn es also eine Möglichkeit mit n = 34 also k = 17 geben würde, dann müsste die Summe der Änderungen dieser 17 Sprungpaare sowohl für die x- Koordinate als auch für die y-Koordinate jeweils 0 sein.

              Man kann nicht alle 17 Sprungpaare aus der "Klasse" g wählen, denn wenn man die Summe der dx zu 0 macht, dann ist gleichzeitig dy ungleich 0.
              (Analog folgt, dass man auch nicht alle 17 Sprungpaare aus der Klasse u wählen kann.)

              Es kann also nur mit Hilfe einer "Mischung" aus den Klassen u und g gelingen beide Koordinatenänderungen gleichzeitig zu 0 zu machen.
               
              Sei U die Anzahl der Sprungpaare aus der Klasse u und G die Anzahl der Sprungpaare aus der Klasse g. ==> U + G = 17

              Damit man durch Mischung beide Koordinaten zu 0 kompensieren kann, muss gelten:  U = 2*G   oder 2*U = 3*G  
               
              U = 2*G führt auf 3*G = 17 (Widerspruch)   ;   2*U = 3*G führt zu 2,5*G = 17 (Widerspruch)

              Somit ist k = 17 nicht möglich ==> Das maximal mögliche n ist 32.

              Die Existenz einer Lösung mit n = 32 kann man (wie von Martina gezeigt) angeben. 

              Übrigens das gezeigte Beispiel im Aufgabentext besteht aus drei Sprungpaaren (k=3) und es gilt G = 1 und U = 2.

[Martina]

Ja. Das dürfte aber in der Argumentation drin sein. Hier  nochmal anders:

Insgesamt gibt es mit dem Endfeld 35 Felder, wovon 17 weiß und 18 schwarz gefärbt werden von mir. Da immer von weiß nach schwarz oder von schwarz nach weiß gesprungen wird, muss ein Doppelfeld leer bleiben. Maximal möglich sind damit 33 Felder. Da allerdings ein Sprung immer von einem weißen auf ein schwarzes Feld oder von einem schwarzen auf ein weißes erfolgt, muss die Maximalzahl gerade sein. Damit ist 32 die Höchstgrenze.

Oder passt der erste Gedanke komplett nicht?

Ich verstehe es immer noch nicht, wie Du da die 34 ausschließt.

[Fanbusfahrer]

Das war ein Fehler von mir. Ich habe eure Lösungen verstanden und meine korrigiert ;-)