witte tabellen
Opgave - NWO 2013 vraag 1
Van een tabel bestaande uit $n$ bij $n$ vierkantjes zijn sommige vierkantjes zwart en zijn de overige vierkantjes wit. Voor ieder tweetal kolommen en ieder tweetal rijen geldt dat de vier vierkantjes op de kruisingen van die rijen en kolommen niet allemaal dezelfde kleur hebben.
Wat is de grootst mogelijke waarde van $n$?
- login om te reageren
Oplossing
Stel dat $n \ge 5$ en er geen vier vakjes geselecteerd kunnen worden zoals in de opgave, met allen hetzelfde kleurr. Dan zijn er minstens 3 vakjes met dezelfde kleur in de eerste rij. Stel WLOG dat deze vakjes wit zijn. Stel ook WLOG dat deze 3 vakjes in de kolommen 1,2,3 liggen.
We bekijken nu kolommen 1,2,3. In elke rij verschillend van 1 kunnen in kolommen 1, 2, 3 hoogstens 1 wit vakje voor komen, anders zou je met die rij en rij 1 4 witte vakjes hebben. Er zijn dus in elke rij onder de eerste, minstens 2 zwarte vakjes tussen de eerste 3 vakjes. Er zijn $\left({}^{3}_{2}\right) = 3$ manieren om 2 zwarte vakjes in 3 vakjes te steken. Er zijn nog minstens 4 rijen verschillend van de eerste. Duivenhok verteld ons dat er dus 2 kolommen moeten zijn met 2 zwarte vakjes in dezelfde kolommen. Dit is echter ook niet mogelijk. Conclusie: als $n \ge 5$ is het onmogelijk.
Voor $n= 4$ volstaat het om een voorbeeld te geven. Hier stellen O's en X'en zwarte en witte vakjes voor.
XXOO
OXXO
OOXX
XOOX