Fibonacci

Fibonacci auf dem Damebrett (Teil 3)


Für eine Beziehung zwischen Fibonaccizahlen und Bridge sieh Jim Loy's Seite.

Zwei Spieler, A(nton) und B(ert), sitzen am Tisch. Auf dem Tisch liegen einige auf einander gestapelten Bierdeckel.
Reihum (Anton fängt an) müssen sie einige Bierdeckel vom Stapel abheben. Derjegene der den letzten Bierdeckel abhebt hat gewonnen.
Es gelten noch die nachfolgenden Regeln:
1. Anton darf am Anfang nicht alle Bierdeckel abheben.
2. Man darf nie mehr Bierdeckel abheben als 2 Mahl die Anzahl, die der Gegner gerade abgehoben hat.
Gibt es eine gewinnende Strategie für einen der beiden Spieler?

Wir werden zeigen dass Bert gewinnen kann wenn der Stapel aus F_n Bierdeckel besteht (für bestimmtes n).
Daraus folgt dass Anton gewinnen kann wenn der Stapel nicht aus F_n Bierdeckel besteht,
denn dann nimmt Anton zuerst soviel Deckel vom Stapel (weniger als die Helfte!), dass F_k Deckel übrig bleiben (für ein bestimmtes k), wonach die Lage entgegengesetzt ist. (Beweis).