Reis em um tabuleiro infinito

(Longlist IMO 1979 - Bulgária) Colocamos 4n + 1 reis em um tabuleiro infinito. Prove que podemos escolher n + 1 deles de modo que não existam dois que se ataquem.

É uma questão que te lembra principio das gavetas, mas é difícil encontrar as gavetas. Mas dado que os números do enunciado são 4n+1 e n+1, suspeitamos que precisaríamos de 4 gavetas. E isso de fato funciona


A ideia é a seguinte: Digamos que cada casa do tabuleiro tem uma coordenada (x,y), onde x,y são inteiros. Repare que para um rei na casa (x,y) atacar um rei na casa (a,b), devemos ter |x-a| ≤ 1 e |y-b|≤ 1. Ou seja, esse rei ataca as casas
(x+1, y+1), (x+1,y), (x+1,y-1), (x,y+1), (x,y-1), (x-1,y+1), (x-1,y), (x-1,y-1)

Assim as gavetas serão:
Gaveta 1: Casas onde x e y são pares
Gaveta 2: Casas onde x é par e y é impar
Gaveta 3: Casas onde x é impar e y é par
Gaveta 4: Casas onde ambos são impares,

Ou seja, duas casas estão na mesma gaveta se as coordenadas correspondentes tem a mesma paridade. Isso significa que duas casas (x,y) e (a,b) que estão numa mesma gaveta não podem se atacar, pois devemos ter |x-a| e |y-b|  ambos pares, e não podemos ter ambos iguais a zero.

Pelo principio das gavetas, Como são 4n+1 reis, existe uma delas que contem pelo menos n+1 reis. Logo, esses reis não se atacam, como queríamos mostrar.