Fibonacci
Bewijs:
Beweis (Mit Verlaufsinduktion): Wir wollen zeigen dass Bert gewinnen kann wenn anfangs Fn (für gewisses n) Deckel auf dem Tisch liegen.
Hier soll n mindestens 3 sein, denn für n=1 oder n=2 handelt es sich um einen "Stapel" mit 1 Bierdeckel. Und mit einem Bierdeckel sind die erforderlichen Bedingungen wiedersprüchlig, denn Anton
darf, wenn er das erste Male dran ist, nicht alle
Deckel abheben, und zur gleichen Zeit muß er mindestens einen Deckel abheben.
Der Beweis wird einfacher wenn wir induktiv die nachfolgende starkere Aussage beweisen:
Behauptung: Bert kann gewinnen wenn Anton anfangs einen Stapel mit Fn (für gewisses n) Deckeln vor sich liegen hat.
Bert nimmt darbei in seinem gewinnenden (= letzten) Zug Fn-1 oder weniger Deckel.
Die Behauptung ist richtig für n=3 und für n=4, denn:
Für n=3 gibt es 2 Deckel. Davon muß Anton 1 abheben und darauf hebt Bert auch 1
(=Fn-1) und Bert gewinnt.
Für n=4 gibt es 3 Deckel. Dann kann Anton 1 abheben und Bert 2(=Fn-1) oder Anton 2 und Bert 1(<Fn-1). In beiden Fällen gewinnt Bert.
Kurz, die Behauptung stimmt für n=3 und für n=4.
Nehm mal an dass wir schon gezeigt haben dass die Behauptung stimmt für alle n<N. Dann wollen wir jetzt zeigen dass die Behauptung auch stimmt für n=N.
Wir wissen dass FN = FN-1 + FN-2.
Wir spalten (im Gedanken) den Stapel in zwei Teile.
Auf dem untersten Teil von FN-1 Deckeln liegen
FN-2 Deckel.
Da Bert immer gewinnen kann mit einem Stapel von FN-2 Deckeln (nach Induktionsunterstellung), kann
er bewirken dass er nach einigen Zügen (wobei der letzte Zug weniger als FN-3 Deckel enthält) noch FN-1 Deckel übrig bleiben
(es sei denn dass Anton bei seinem ersten Zug FN-2 oder mehr Deckel abhebt, aber dann gewinnt Bert indem er alle übrigen Deckel abhebt;
Bert's gewinnende Zug besteht dann aus weniger als FN-1 Deckeln).
Bert gewinnt unabhängig von Anton's nächsten Zug, denn Bert kann immer gewinnen mit einem Stapel von FN-1 Deckeln (nach der Hypothese),
und Anton darf nicht alle Deckel abheben, denn 2*FN-3 < FN-1.