Q10 Matemática  (JBMO ShortLists 2008)

Em um tabuleiro $5\times 5$, marcadores brancos $n$ são posicionados, cada marcador em um quadrado distinto $1\times 1$. Uma criança esperta recebeu a tarefa de recolorir de preto o maior número possível de marcadores, da seguinte maneira: um marcador branco é retirado do quadro, é colorido de preto e depois colocado de volta no quadro em um quadrado vazio, de modo que nenhum dos quadrados vizinhos contém um marcador branco (dois quadrados são chamados de vizinhos se compartilham um lado comum). Se for possível que a criança consiga colorir todos os marcadores de preto, dizemos que o posicionamento inicial dos marcadores foi bom. a) Prove que se $n=20$, então existe um bom posicionamento inicial. b) Prove que se $n=21$, então não existe um bom posicionamento inicial.