Fibonacci

Bäume und Bits (Teil 2)


Wir widmen uns wieder dem Problem der Stammbäume aus der Einführung.



Sieh da, der Stammbaum eines Kaninchenpaars in dem Problem von Fibonacci. Eine 0 bezeignet ein soeben geborenes Kaninchenpaar und eine 1 bezeignet ein Kaninchenpaar dass minimal 1 Jahr alt is. Zugleich stellt er den Stammbaum einer Drohne dar. Eine 0 ist eine Drohne und eine 1 ein Bienenweibchen.


Die n-te Reihe (n>1) des Stammbaumes enthält die ersten F_n Ziffern der unendlichen Zahlenfolge 1 0 1 1 0 1 0 1 1 0 1 1 ... .
f(k) ist die k-te Ziffer dieser Zahlenfolge. Wann ist f(k)=1? Die Antwort ist: wenn k = 1,3,4,6,8,9,11,... .
Wir haben gezeigt dass die i-te Zahl aus 1,3,4,6,8,9,11,...      [iφ] ist.
Diese Zahlenfolge ist identisch mit der Folge a₁,a₂,a₃, ... der vorigen Seite.
Die Zahlenfolge b₁,b₂,b₃, ... enthält alle Zahlen die nicht in der a-Folge enthalten sind.

Zwei Spieler, A(nke) und B(ea), sitzen am Tisch. Auf dem Tisch liegen zei Stapel Bierdeckel.
Der Reihe nach (Anke beginnt) müssen Sie einige Bierdeckel von den Stapeln abnehmen. Diejenige die den letzten Bierdeckel aufhebt hat gewonnen.
Es gilt noch die Regel:
Sie dürfen eine beliebige Anzahl Deckel von einem der beiden Stapel abnehmen oder von beiden Stapeln gleich viele. Gibt es eine gewinnende Strategie für einen der beiden Spieler?

Die Antwort auf dieser Frage lautet wie folgt: Bea kann immer gewinnen wenn anfänglich einer der beiden Stapel a_n Deckel enthält und der andere b_n (für gewisses n), sonst kann Anke gewinnen.
Wie muß Bea handeln wenn die Stapel a_n und b_n Deckel enthalten und Anke an der Reihe ist? Wenn Anke gleich viele Deckel von beiden Stapeln abhebt oder einige von den a_n Deckeln, dann ist Bea immer in der Lage soviel Deckel vom anderen Stapel abzunehmen, dass die Stapel wieder a_j und b_j Deckel enthalten (für gewisses j).
Wählt Anke nur Deckel vom Stapel mit b_n Deckeln, dann kann Bea soviel Deckel von beiden Stapeln aufheben, dass die Stapel wieder a_j und b_j Deckel enthalten (für gewisses j).


Wir können dieses (etwas verwickelt aussehende) Rezept einsichtig machen indem ein ganz anderes Spiel betrachtet wird!
Der Reihe nach müssen A(nke) und B(ea) die gleiche Dame auf dem Schachbrett versetzen. Die Dame darf in diesem Spiel nur in die Richtungen Süd, West oder Süd-West versetzt werden. Diejenige die die Dame zum linker-unteneck (A1 in der Schachsprache) versetzt gewinnt die Partie. Die Anfangsposition der Dame kann man frei wählen.
N.B. Wir brauchen uns nicht auf das 8x8 Brett zu beschränken. Wir können z.B. auch ein 100x100 Brett nehmen.
Die Übereinstimmung mit dem vorigen Spiel ist wie folgt:
Wenn die Dame sich auf dem Quadrat (3,7) befindet (in Schachsprache: auf d8), dann stimmt das mit einem Stapel von 3 Bierdeckeln und einem von 7 Deckeln im vorigen Spiel überein.
Ein Süd-West-Zug stimmt mit 'von beiden Stapeln gleich viel abheben' überein; ein West-Zug mit 'vom Stapel mit 3 Deckeln einige abnehmen', und ein West-Zug mit 'vom Stapel mit 7 Deckeln einige abnehmen'.
Die drei Linien durch (0,0) in der grafischen Darstellung des Schachbretts durchkreuzen genau die Quadrate die die Eigenschaft haben dass man ab dort in einem Zug gewinnen kann.
Die roten Quadrate auf (2,1) und (1,2) sind sodann die Stellen ab wo ein Spieler nur einen Zug machen kann zu einem Quadrat wodurch gerade eine Linie gezeignet ist, also wenn man an der Reihe ist und die Dame steht auf einem roten Quadrat, dann verliert man immer.
Die 3 Linien die starten ab (2,1) und (1,2) sind die Linien durch alle Quadrate ab wo ein Spieler in einem Zug die Dame in dat rote Quadrat (1,2) oder (2,1) versetzen kann. Das sind also wieder gewinnende Positionen. So kann man weiter gehen und alle gewinnenden oder verlierenden Stellen finden.

Die a_n und die b_n sind im Schachdiagramm zurück zu finden und die Lösung aus dem vorigen Paragraphen stimmt mit diesem Diagramm überein. (Beweis)