Ich komme auf 32 Quadrate. Habt ihr (die 33er) bedacht, dass der Weg auf demselben Feld enden soll, an dem er angefangen hat? Dann muss es aufgrund des Färbe-Prinzips eine gerade Anzahl sein.
In meinem Beweis fehlte nur noch ein Puzzleteil für ein Argument, warum auch die Anzahl der horizontalen und der vertikalen Züge gerade sein muss.
Ich habe festgestellt, dass ich "Schritte" und Sprünge gleichbedeutend benutze, bitte ignorieren...
Ich fand es cool, dass das Färbungsprinzip gerade nicht funktioniert. In meiner Begründung habe ich auch das gleiche Argument wie schon beschrieben genutzt. Ich bezeichne mit A die Felder in der ersten und letzten Reihe, mit B die Felder in den mittleren Reihen. Ein Schritt von A nach A kann nur ein kurzer Schritt sein. Wenn ich alle Felder betreten möchte, dann muss die Anzahl an A-A Sprüngen zwei größer als die der B-B Sprünge sein (am Ende ist das doppeltes abzählen). Aber das heißt, es müsste zwei A-A Sprünge geben, zwischen denen nur A-B oder B-A Sprünge sind, und zwar immer in Paaren und in dieser Reihenfolge. Damit ist eine gerade Anzahl an Sprüngen zwischen ihnen, und sie können nicht beide kleine Sprünge sein (zwischen zwei kleinen Schritten ist immer eine ungerade Anzahl an Schritten), ein Widerspruch.
Eine ungerade Anzahl an Sprüngen geht nicht (z.B. zu zeigen durch Schachbrettfärbung), damit ist 32 das Maximum. Eine 32er Folge ist schnell gefunden, wie auch die vorangegangenen Beiträge schon zeigen.
Für mich war die Aufgabe wirklich cool, gerade weil die sonst übliche Schachbrettfärbung nicht gereicht hat, am Ende aber eine ähnliche und saubere Argumentation klappt.
(01-02-2024, 09:59 AM)st1974 schrieb: Ich komme auf 32 Quadrate.
In meinem Beweis fehlte nur noch ein Puzzleteil für ein Argument, warum auch die Anzahl der horizontalen und der vertikalen Züge gerade sein muss.
(01-01-2024, 09:06 PM)Mathe Juergen schrieb: 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.
Der Beweis kann so nicht funktionieren, da du an keiner Stelle benutzt, welche Felder genau fehlen. Es ist sehr wohl möglich, auf einer Runde genau 34 Felder zu betreten. Die zwei fehlenden Felder sind dann allerdings nicht zwei Felder in den mittleren beiden Reihen, sondern andere. Hier ist eine Möglichkeit mit 34 Schritten, die an den fehlenden beiden Feldern oben in der Mitte beginnt:
Diese Aufgabe gehört für mich zu den besten in diesem Jahr. Ich habe sehr lange über eine wasserdichte Begründung nachgedacht, warum 34 nicht gehen.
Zunächst habe ich es auch mit Färbungen versucht - das ist ja der Standard Trick - hier lässt sich ganz einfach 33 ausschließen. Auch vier verschiedene Farben haben nicht zum Ziel geführt.
Die Idee von Martina: Einteilung in 16 oben-unten Rand und 16 mittlere Felder ist prima und letztendlich dann ganz einfach nachzuvollziehen!! Super.
Murks Idee führt letztlich auf das Gleiche...
Nach dieser Begründung ist dann auch sofort klar, dass jeder 34 ger Weg, der dann zwingend kein Kreisweg ist (und da gibt es einige verschiedene!!) seinen Anfang und sein Ende auf oberen oder unteren Randfeldern haben muss! Hier finden sich nicht geschlossene Wege, deren Anfang und Ende beide oben bzw unten sind, aber auch Wege, die oben beginnen und unten enden (bzw umgekehrt, man kann ja rückwärtslaufen).
Spannend finde ich noch folgende Zusatzaufgabe:
Wie viele echt verschiedene 32ger Kreiswege (bzw nicht geschlossene 34ger Wege), die man nicht über Spiegelungen und Drehungen überführen kann (warum denke ich gerade an A17;-)) gibt es denn?
Mit ein bisschen Probieren habe ich jetzt mit einer Schrittfolge einen geschlossenen 32er Weg, einen offenen 34er Weg und einen geschlossenen 36er Weg gefunden.
Nur die Hintergründe sind unterschiedlich gefärbt.
(01-01-2024, 09:06 PM)Mathe Juergen schrieb: 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.
Der Beweis kann so nicht funktionieren, da du an keiner Stelle benutzt, welche Felder genau fehlen. Es ist sehr wohl möglich, auf einer Runde genau 34 Felder zu betreten. Die zwei fehlenden Felder sind dann allerdings nicht zwei Felder in den mittleren beiden Reihen, sondern andere. Hier ist eine Möglichkeit mit 34 Schritten, die an den fehlenden beiden Feldern oben in der Mitte beginnt:
(01-03-2024, 06:17 PM)Pierrot schrieb: Spannend finde ich noch folgende Zusatzaufgabe:
Wie viele echt verschiedene 32ger Kreiswege (bzw nicht geschlossene 34ger Wege), die man nicht über Spiegelungen und Drehungen überführen kann (warum denke ich gerade an A17;-)) gibt es denn?
Da jeder 32er Weg ein Zyklus ist und abwechselnd eine Pferd-/König-Bewegung ist und jedes Feld der mittleren Zeilen sicher abgelaufen wird, kann man oBdA annehmen, dass man bei (0,1) startet [x = 0, y = 1... links unten ist bei mir (0,0)] und einen Pferde-Bewegung macht.
Mein Programm hat dafür bisher 77'207 verschiedene Wege gefunden xD
Wenn man in dem Zyklus nicht bei (0,1) startet, sondern bei einem beliebigen anderen Feld und nicht mit einer Pferde-Bewegung sondern mit einer König-Bewegung, so muss man diese Zahl noch mit 64 multiplizieren. Das macht 4'941'248 Wege. Um Drehungen und Spiegelungen auszuschließen (zum Glück kann kein Weg rotations-/achsensymmetrisch sein) muss man noch durch 4 teilen (wenn ich mich nicht vertue) - macht min 1'235'312 Wege.
Edit: Nach 3,6 Millionen Versuchen hat mein Programm schon 198'090 Wege wie oben gefunden, wovon 95'460 verschieden waren. Somit gibt es insgesamt mindestens schon 1'527'360 verschiedene Wege wenn der erste Move und das Startfeld nicht festgelegt ist.
![[Bild: img.php?image=2181_21_m5uo.png]](https://beta.uyl.me/lab/img.php?image=2181_21_m5uo.png)
![[Bild: img.php?image=6761_21b_cmnc.png]](https://beta.uyl.me/lab/img.php?image=6761_21b_cmnc.png)
