Fibonacci

Beweis:


Wir zeigen dass die Koordinaten der roten Quadrate (a_n, b_n) oder (b_n, a_n) sind.
(Mit Verlaufsinduktion). Es ist sonnenklar dass die zwei roten Quadrate die zuerst eingefärbt werden die Koordinaten (a₁, b₁) = (1, 2) und (b₁, a₁) besitzen.
Setze mal voraus dass die Quadrate (a_k, b_k) und (b_k, a_k) schon eingefärbt sind für k < K.
Dann sind dabei Linien gezogen über die folgenden Quadrate: (a_k, j), (b_k, j), (j, a_k), (j, b_k), (a_k + j, b_k + j) und (b_k + j, a_k + j) für alle k < K und alle j > 0.
Wir suchen nun ein Paar (a,b), das nicht zu einer dieser Formen gehört, mit einem möglichst kleinen Wert für a.
Der kleinste Kandidat für a ist a_K (laut Definition a_K). Gibt es ein b so dass (a_K, b) ein noch nicht durschnittenes Quadrat darstellt?
Auch b ist nicht kleiner als a_K. Wir betrachten nun den Kandidaten (a_K, a_K + r), mit 0 ≤ r < K.
Nun ist (a_K, a_K + r) = (a_r + j, b_r + j) mit j = a_K - a_r. Aber das ist nicht erlaubt.
Bewährt sich (a_K, b_K)? Ja, denn wenn (a_K, b_K) = (a_m + j, b_m + j) mit j > 0 und m < K, dann ist K = b_K - a_K = b_m - a_m = m und j = 0. Ein Widerspruch.
(a_K, b_K) ist folglich das kleinste Quadrat dass noch nicht durchstrichen ist (die kleinste x-Koordinate gefolgt von der kleinsten y-Koordinate) und ähnlicherweise ist (b_K, a_K) das kleinste Quadrat, wobei die kleinste y-Koordinate gefolgt wird von der kleinsten x-Koordinate.
Damit ist der Beweis vollständig.

Die roten Quadrate bilden eine Art Trichter. Innerhalb dieses Trichters gehen die Linien von den roten Punkten abschüssig ins Unendliche. Befinden wir uns innerhalb dieses Trichters, (was geschieht wenn man vom Kartenstamm (a_n, b_n) (oder (b_n, a_n)) nur abhebt von den b_n Bierfiltzen), dann können wir von beiden Stapeln soviel abheben dass wir wieder ein rotes Quadrat bekommen. In allen anderen Fällen ist es immer möglich ein rotes Quadrat zu bekommen durch abheben einiger Filze von einem der Stapel.