Fibonacci

Bewijs:


We tonen aan dat de rode vakjes coördinaten (a_n, b_n) of (b_n, a_n) bezitten.
(Met verloopsinductie). Het is duidelijk dat de twee rode vakjes die het eerst worden ingevuld als coördinaten hebben (a₁, b₁) = (1, 2) en (b₁, a₁).
Stel de vakken (a_k, b_k) en (b_k, a_k) zijn reeds ingekleurd voor k < K.
Dan zijn daarbij lijnen getrokken over de volgende vakken: (a_k, j), (b_k, j), (j, a_k), (j, b_k), (a_k + j, b_k + j) en (b_k + j, a_k + j) voor alle k < K en alle j > 0.
We zoeken nu een paar (a,b), niet behorend tot een van deze vormen, met een zo klein mogelijke waarde van a.
De kleinste kandidaat voor a is a_K (zie definitie a_K). Is er een b te vinden zo dat (a_K, b) een nog niet doorsneden vakje representeert?
Ook b is minstens a_K. We bekijken nu de kandidaat (a_K, a_K + r), met 0 ≤ r < K.
Nu is (a_K, a_K + r) = (a_r + j, b_r + j) met j = a_K - a_r. Maar dat is niet toegestaan.
Voldoet (a_K, b_K)? Ja, want als (a_K, b_K) = (a_m + j, b_m + j) met j > 0 en m < K, dan is K = b_K - a_K = b_m - a_m = m en j = 0. Contradictie.
Dus is (a_K, b_K) het kleinste vakje dat nog niet is doorgestreept (kleinste x-coördinaat gevolgd door kleinste y-coördinaat) en analoog (b_K, a_K) het kleinste vakje, waarbij de kleinste y-coördinaat gevolgd wordt door de kleinste x-coördinaat.
Hiermee is het bewijs voltooid.

De rode vakjes vormen een soort trechter. Binnen deze trechter lopen de lijnen vanuit de rode punten schuin omhoog naar oneindig. Bevinden we ons binnen deze trechter, (hetgeen geschiedt als je van de kaartstapeltjes (a_n, b_n) (of (b_n, a_n)) enkele van de b_n filtjes afneemt), dan kunnen we van beide stapeltjes zoveel afnemen dat we weer in een rood vakje belanden. In alle andere gevallen is het altijd mogelijk om door het afnemen van enkele filtjes van een van beide stapels, in een rood vakje te belanden.