Gepensioneerde vorsten hebben tijd om een spelletje te spelen

Opgave - IMO 2018 dag 2 vraag 1

Een plek is een punt $(x,y)$ in het vlak zodat $x$ en $y$ beide gehele getallen zijn met $1 \leq x,y \leq 20$.

Bij aanvang zijn alle $400$ plekken leeg. Albert en Beatrix plaatsen om de beurt een steen, waarbij Albert begint.
Als Albert aan de beurt is, plaatst hij een nieuwe rode steen op een lege plek zodanig dat de afstand tussen elke twee plekken met een rode steen niet gelijk is aan $\sqrt{5}$.
Als Beatrix aan de beurt is, plaatst zij een nieuwe blauwe steen op een lege plek.
(Een plek met een blauwe steen mag op willekeurige afstand van een andere niet-lege plek liggen.)
Ze stoppen zodra een speler geen steen meer kan plaatsen.

Bepaal de grootste $K$ zodanig dat Albert gegarandeerd minstens $K$ rode stenen kan plaatsen, hoe Beatrix haar blauwe stenen ook plaatst.

Oplossing

Eerst tonen we aan dat $K=100$ mogelijk is. Als Albert alle plekken $(x,y)$ waarvoor $x+y$ even zou kleuren, dan heeft hij geen plekken gekleurd die op een afstand $\sqrt{5}$ van elkaar liggen. Immers, moest er een plek $(x',y')$ op een afstand van $\sqrt{5}$ van $(x,y)$ liggen, dan zou $x'=x\pm 2$ en $y'=y\pm 1$ of $x'=x\pm 1$ en $y'=y\pm 2$ moeten zijn. Maar dan is $x'+y'=x+y\pm 1\pm 2$ oneven, contradictie. Er zijn 200 van deze plekken en de enige manier waarop Beatrix dit aantal punten kan verminderen is door ook telkens één van deze plekken te kleuren, waardoor Albert 100 plekken kan kleuren.

We tonen aan dat dit aantal maximaal is. Hiervoor bekijken we eerst de situatie met 16 plekken $(x,y)$ waarvoor $1\le x,y \le 4$. We kunnen deze plekken in vier groepen van vier verdelen, zoals op de tekening (de kleuren dienen enkel om de groepjes aan te duiden en staan los van de kleuren in de opgave). Telkens als Albert een plek van een groepje kleurt zorgt dit ervoor dat hij twee andere plekken van het groepje niet meer kan kleuren omdat ze op een afstand van $\sqrt{5}$ van de net gekleurde plek liggen. Als Beatrix nu telkens de vierde plek van de groep kleurt, dan kan Albert na deze beurt geen plek van deze groep kleuren. Aangezien raster van $4\times 4$ plekken 4 groepjes telt, kan Albert maximaal 4 plekken kleuren als Beatrix optimaal speelt. We kunnen het $20\times 20$ raster verdelen in 25 $4\times 4$ rasters. Aangezien Albert volgens de strategie hierboven maximum 4 plekken kan kleuren in elk van deze kleine rasters, is $K$ maximaal gelijk aan $25\cdot 4=100$.