Züge um mit einem Springer Schachfeld zu Überqueren

Question

Guten Morgen, folgende Aufgabe:

Aufgabe: Ein Springer steht in einem Schahfeld beliebiger quadratischer Größe in einer der oberen Ecken.

Er soll nun in die obere Ecke auf der anderen Seite bewegt werden.

Wie viele Züge sind in Abhängigkeit von der Größe des Schachfelds dafür mindestens notwendig?

Was mir bisher dazu eingefallen ist:

Der Springer kann immer zwei mögliche Züge machen:

1) Ein Feld in die Horizontale Richtung, dafür bewegt er sich um zwei nach oben oder unten (a)

2) Zwei Felder in Horizontale Richtung, dafür bewegt er sich um eins nach oben oder unten. (b)

Sei k die Größe des Schachfelds so müsste für die Bewegung entlang der horizontalen gelten:

a + 2b = k-1

Um jetzt nach a oder b aufzulösen bräuchte ich aber eine zweite Gleichung, die habe ich aber noch nicht. Meine Idee wäre gewesen, jetzt die vertikale Bewegung zu betrachten, diese muss am Ende aber ja gleich null sein.

Ich würde mich sehr über Hilfe freuen :)

Answer 1

n = 1 → k = 0

n = 2 → k = ---

n = 3 → k = 2

n = 4 → k = 5

Führe das mal fort bis du eine schöne Struktur erkennst. Überlege auch ob ich hier bereits die kleinstmögliche Zuganzahl notiert habe.

n = 5 → k = ...

Comments

Hi, danke für deine Antwort :) Über Teilerrestbetrachtungen bin ich jetzt zur Lösung gekommen :)

Answer 2

Hallo,

sei \(k\) die Anzahl der Felder in einer Reihe des Schachbretts, so ist die Mindestanzahl \(n\) der Züge, die ein Springer benötigt, um von einer Ecke in die benachbarte Ecke zu kommen:$$n = k -1 - 2\left\lfloor \frac {k-1}4 \right\rfloor \quad k \ge 3 \land k \ne 4 $$Und die Ausnahme \(n(4)=5\) ist nur deshalb eine Ausnahme, weil der Springer das Schachbrett verlassen müsste, um das Zielfeld in drei Zügen zu erreichen. Ein Schachbrett \(4 \times 4\) ist dafür schlicht zu klein.

Mehr dazu ggf. heute Abend.

Hier hatte ich schon mal was zum Thema geschrieben ...