spelen met de letters van IMO

We bewijzen dat $n$ een negenvoud moet zijn.

Allereerst is het duidelijk dat $n$ een drievoud is. Immers, moest het dit niet zijn, dan is het onmogelijk om $\frac 13$ van een rij te nemen. Zij dus $n=3 k$. Noem nu een diagonaal die een veelvoud van $3$ is een goede diagonaal. Noem een goed vakje een vakje dat op twee goede diagonalen ligt. Nu bewijzen we volgende lemma's:

Lemma 1: als $n$ voldoet, voldoet $a\cdot n$ ook.

Bewijs: verdeel de $an \times an$-tabel in $a$ verschillende $n \times n$-tabellen. Vul deze allemaal in op de manier waarop je de tabel invult wanneer ze voldoet. Dan zal ook deze tabel voldoen, aangezien in elke rij of kolom in elke $n \times n$-tabel de voorwaarden voor de rijen of kolommen gelden, en dus ook in de $an \times an$-tabel, en elke goede diagonaal zal dan, omdat $n$ een drievoud is, bestaan uit afzonderlijke goede diagonalen van de $n \times n$-tabellen.

Lemma 2: het totaal aantal goede vakjes is $k^2$.

Bewijs: Om dit in te zien kun je de tabel verdelen in kleine $3 \times 3$-tabellen. Je hebt er dan $k^2$ en binnen elke $3\times 3$-tabel is exact één vakje een element van één goede diagonaal van de eerste soort en één goede diagonaal van de tweede soort: immers, door de twee goede diagonalen binnen de $3\times 3$-tabel door te trekken, bekomen we twee nieuwe goede diagonalen, en bij de andere niet, want dan zal het aantal vakjes geen drievoud zijn. De goede vakjes zelf zijn dus ook exact de middelpunten van de $3\times 3$-tabellen. Verder stellen we $i$ als het aantal van deze vakjes met de letter $I$.

Lemma 3: Elke letter komt $k^2$ keer voor op een diagonaal van één soort.

Bewijs: we kunnen het totaal aantal vakjes op een goede diagonaal van één soort als volgt berekenen: #vakjes$=\sum_{j=1}^{k}{3j}+\sum_{j=1}^{k-1}{3j}=3 k^2$. Omdat één derde hiervan een bepaalde letter moet zijn, komt elke letter $k^2$ keer voor.

Lemma 4: Het aantal letters $I$ die op één van de goede diagonalen ligt is $2 k^2-i$.

Bewijs: dit is gewoon het aantal keer dat het op de diagonalen van de eerste soort voorkomt plus het aantal keer dat het op de diagonalen van de tweede soort voorkomt min het aantal keer dat het dubbel geteld wordt.

Lemma 5: Het aantal letters $I$ die niet op een goede diagonaal vallen is $2 k^2-2i$.

Bewijs: als een vakje niet op een goede diagonaal ligt, ligt het in één van de $k$ rijen van goede vakjes: immers, dan moet het in de $3\times 3$-tabel een zijde gemeenschappelijk hebben met het middelste vakje, aangezien de schuine allemaal op een goede diagonaal liggen. Noteer met $i_n$ het aantal letters $I$ op de goede vakjes op de $n^{de}$ rij van die vakjes als $0 < n \leq k$ en de $n^{de}$ kolom als $k < n \leq 2k$. Omdat in elke rij de letter $I$ $k$ keer voorkomt, is het aantal letters $I$ die niet op een goede diagonaal vallen gelijk aan:

$\sum_{j=1}^{2k}(k-i_j)$
$=2 k^2-2 \sum_{j=1}^k{i_j}$
$=2 k^2-2 i$.

Lemma 6: $i=\frac{k^2}{3}$

Omdat er $3 k^2$ letters $I$ in totaal zijn, moet volgens vorige twee lemma's volgende gelijkheid gelden: $3 k^2=4 k^2-3 i \Leftrightarrow i=\frac{k^2}{3}$.

Uit lemma 6 volgt nu dat noodzakelijk $3 \mid k$. Het enige wat nog te bewijzen is, is dat een $9 \times 9$-tabel juist kan worden ingevuld wegens lemma 1.
Dit is zo, want bvb.
$OOOMMMIII$
$IIIOOOMMM$
$MMMIIIOOO$
$OOOMMMIII$
$IIIOOOMMM$
$MMMIIIOOO$
$OOOMMMIII$
$IIIOOOMMM$
$MMMIIIOOO$
voldoet.