Torens op een schaakbord

Noteer $k(n)$ als de waarde van $k$ voor $n$. Noem een $k \times l$-gebied waarbij op geen van zijn eenheidsvierkantjes een toren staat leeg.

We zullen bewijzen dat $k(n)=\left \lfloor \sqrt{n+1} \right \rfloor$ aan de hand van drie lemma's:

Lemma 1: $k(n-1) \le k(n) \le k(n-1)+1$ voor alle $n \ge 3$.

Bewijs: (1) Beschouw een willekeurige vreedzame opstelling van een $n \times n$-schaakbord. We weten dat er een toren in rij $n$ staat omdat de opstelling vreedzaam is. Beschouw het $n-1 \times n-1$-schaakbord dat verkregen wordt door de toren in rij $n$ weg te nemen, evenals rij $n$ en de kolom waar de toren in staat. We weten dat zich hier een leeg $k(n-1) \times k(n-1)$-vierkant bevindt. Voeg nu de verwijderde toren, rij en kolom weer in. Omdat de toren op rij $n$ staat, weten we dat deze zich niet in dit vierkant kan bevinden. De terug ingevoegde rij kan eveneens geen invloed hebben, maar de kolom wel: deze kan het vierkant onderbreken. Omdat de kolom echter leeg is (op het onderste vakje na), zal dit enkel een extra lege kolom toevoegen en krijgen we een leeg $k(n-1) \times k(n-1)+1$-gebied. Dit gebied bevat een leeg $k(n-1) \times k(n-1)$-vierkant, dus moet $k(n-1) \le k(n)$.

(2) Stel dat $k(n) \ge k(n-1)+2$. Beschouw een $n^2+1 \times n^2+1$-bord. Verwijder de bovenste rij en meest rechtse kolom. Verdeel het $n^2 \times n^2$-bord dat overblijft in $n^2$ kleine $n \times n$-borden, op zo'n manier dat er geen enkele overlap is. Indien er geen lege $n \times n$-vierkanten zijn, moeten er zich in elk van deze gebieden een toren bevinden, dat zijn dus $n^2$ torens. De overgebleven toren voor het volledige $n^2+1 \times n^2+1$-bord moet zich dan in de rechterbovenhoek bevinden; het moet immers in de bovenste rij en meest rechtse kolom staan, want daar zijn nog geen torens. Beschouw nu rij $n+1$. Hier moet ergens een toren in staan, binnen een $n \times n$-vierkant. Boven deze toren zijn er nog $n$ rijen: binnen de $n$ kolommen van het $n \times n$-vierkant waar de toren in staat, moeten deze allemaal leeg zijn; er stond immers slechts één toren in het vierkant en in de bovenste rij tot en met kolom $n^2$ staat ook geen toren. Vandaar is er toch een leeg $n \times n$-vierkant en hebben we contradictie; het vierkant bestaat altijd.

Om de volgende twee lemma's te bewijzen, is het handig om het schaakbord voor te stellen als $n \times n$-matrix. Hierbij staat $0$ in de matrix voor een leeg vakje op het schaakbord en $1$ in de matrix staat voor een toren op het schaakbord.

Lemma 2: $k(n^2+1) \ge n$.

Bewijs: Beschouw een $n^2+1 \times n^2+1$-bord. Verwijder de bovenste rij en meest rechtse kolom. Verdeel het $n^2 \times n^2$-bord dat overblijft in $n^2$ kleine $n \times n$-borden, op zo'n manier dat er geen enkele overlap is. Indien er geen lege $n \times n$-vierkanten zijn, moeten er zich in elk van deze gebieden een toren bevinden, dat zijn dus $n^2$ torens. De overgebleven toren voor het volledige $n^2+1 \times n^2+1$-bord moet zich dan in de rechterbovenhoek bevinden; het moet immers in de bovenste rij en meest rechtse kolom staan, want daar zijn nog geen torens. Beschouw nu rij $n+1$. Hier moet ergens een toren in staan, binnen een $n \times n$-vierkant. Boven deze toren zijn er nog $n$ rijen: binnen de $n$ kolommen van het $n \times n$-vierkant waar de toren in staat, moeten deze allemaal leeg zijn; er stond immers slechts één toren in het vierkant en in de bovenste rij tot en met kolom $n^2$ staat ook geen toren. Vandaar is er toch een leeg $n \times n$-vierkant en hebben we contradictie; het vierkant bestaat altijd.

Lemma 3: $k(n^2) \le n-1$.

Bewijs 1: we beschouwen de vreedzame opstelling waarbij de enen op coördinaten $(1, 1)$, $(2, n+1)$,$(3, 2n+1)$, ..., $(n, n^2-n+1)$, $(n+1, 2)$, $(n+2,n+2)$, ..., $(n^2, n^2)$ staan (zo dat de kolomcoördinaten van rijcoördinaten $jn+1, jn+1, ..., jn+n$ allemaal congruent zijn modulo $n$). Met deze constructie zal er voor elke willekeurige opeenvolgende rijcoördinaten $j, ..., j+n-1$ en opeenvolgende kolomcoördinaten $i, ..., i+n-1$ een coördinaat $(x,y)$ zijn met een toren zodat $j \le x \le j+n-1$ en $i \le y \le i+n-1$. We zien namelijk dat de kolomcoördinaten van de torens met deze rijcoördinaten hoogstens twee verschillende resten hebben modulo $n$, die hoogstens één verschilt, zeg $a$ en $a+1$. Stel nu dat de toren met kolomcoördinaat de rest $a$ modulo $n$ binnen $[i, i+n-1]$ zijn rijcoördinaat niet binnen $[j, j+n-1]$ heeft, dan heeft die met rest $a+1$ dat wel: deze bevindt zich immers $n$ eenheden lager of hoger qua rijcoördinaat en die met rest $a$ bevindt zich er max $n$ boven of onder (al naargelang $a=n-1$ of niet). Ook omgekeerd geldt dit. Daarmee is het lemma bewezen: er bestaat hier geen leeg $n \times n$-vierkant.

Bewijs 2:
Verdeel het $n^2 \times n^2$-bord in $n^2$ kleine $n \times n$-vierkanten, op zo'n manier dat er geen overlap is. Noem deze vierkanten goed. Nu plaatsen we in de linkerbovenhoek een toren en we gaan op de volgende manier verder met het plaatsen van torens, zodanig dat er in elk goed vierkant één toren staat:

- Wanneer we van een goed vierkant naar het goede vierkant rechts gaan, plaatsen we daar een toren die relatief gezien in dezelfde kolom staat, maar één rij naar beneden is verschoven;

-Wanneer we van een goed vierkant naar het goede vierkant er net onder gaan, plaatsen we daar een toren die relatief gezien in dezelfde rij staat, maar één kolom naar rechts is verschoven.

Het is niet moeilijk in te zien dat deze twee operaties commutatief en associatief zijn; vandaar zal de configuratie exact uitkomen en door het opschuiven is ze bovendien vreedzaam. Bovendien zal binnen twee aangrenzende goede vierkanten de afstanden tussen de rijen/kolommen waar de torens staan exact $n$ of $1$ zijn (naargelang het ernaast of erbovenof eronder is).

Beschouw nu een willekeurig $n \times n$-vierkant. We onderscheiden drie gevallen:

(1) Het vierkant valt samen met een goed vierkant. In dit geval is het zeker niet leeg.

(2) Het vierkant valt binnen twee goede vierkanten. Ook in dit geval kan het niet leeg zijn; immers, de rijen of kolommen vallen samen met die van de goede vierkanten, zeg WLOG rijen (kolommen verloopt analoog). Dan zal voor de $n$ kolommen gelden dat één van de torens hierbinnen valt: de afstand tussen de kolommen van beide torens is $n$, dus het totaal aantal kolommen tussen of gelijk aan die van de torens is $n+1$. Het vierkant beslaat slechts $n$ kolommen en de totale figuur beslaat er $2n$: wegens het duivenhokprincipe hebben ze dus minstens één overlappend element, dus zal één van de torens binnen het vierkant vallen.

(3) Het vierkant valt binnen vier goede vierkanten. Beschouw de twee bovenste goede vierkanten; om dezelfde reden als bij (2) overlapt de kolom van één van hun torens met een kolom van het vierkant. Zeg toren $A_1$. Ook voor de onderste twee geldt dit, zeg hier dat de toren $A_2$ is. Analoog kunnen we dit zeggen voor de rijen: zeg dat de rijen van toren $B_1$ en $B_2$ binnen die van het vierkant vallen, met $B_1$ voor de twee links en $B_2$ voor de twee rechts. Als nu één van $B_1$ of $B_2$ gelijk is aan $A_1$ of $A_2$, zijn we klaar, want dan zal die toren binnen het vierkant vallen. Veronderstel dus dat dit niet zo is: dan zijn $A_1$, $A_2$, $B_1$, $B_2$ exact de vier torens op de goede vierkanten. Deze kunnen we via matrixnotatie benoemen met $a_{11}, a_{12}, a_{21}, a_{22}$. Stel nu dat $a_{11}=A_1$. Nu moet één van $a_{21}$ en $a_{22}$ gelijk zijn aan $A_2$. Dit kan echter niet $a_{22}$ zijn, omdat de afstand tussen $a_{11}$ en $a_{22}$ groter is dan $n$. Dus is het $a_{21}$. Maar dit kan evenmin, want dan vallen $B_1$ en $B_2$ beiden in het rechtervierkant, wat niet kan! Dus moet $a_{12}=A_1$. Analoog aan hiervoor moet dan $A_2=a_{21}$. Nu zal echter $B_1=a_{11}$ en $B_2=a_{22}$. Dit is ook onmogelijk, omdat ook de afstand tussen hun kolommen groter is dan $n$! We concluderen dus dat er ook hier een toren moet bestaan die binnen het vierkant valt, dat dus niet leeg is.

Uit lemma 1, 2 en 3 leiden we nu af dat $k(n^2)=n-1$ en $k(n^2+1)=n$; deze kunnen immers niet meer dan één verschillen. Als er zich tussen $n^2+1$ en $(n+1)^2$ een $n^2+l$ bevindt waarbij $k(n^2+l) \ge n+1$, dan zal $k((n+1)^2) \ge n+1$ wegens lemma 1, wat wegens lemma 3 contradictie oplevert. Dus de waarde van $k(n)$ wordt één hoger dan en slechts dan als $n$ van de vorm $q^2+1$ is, waar $k(q^2+1)=q$. Vandaar is $k(n)=\left \lfloor \sqrt{n-1} \right \rfloor$. Q.E.D.