(OBM 2017 - 2)

Seja n>1 um inteiro e considere um tabuleiro nxn, em que algumas das n² casas foram pintadas de pretos, e as restantes foram pintadas de branco. Prove que é possível escolhermos uma das n² casas do tabuleiro, de modo que, ao removermos completamente a linha e a coluna que a contém, haja um número diferente de casas pretas e de casas brancas, dentre as (n-1)².

Seja n um número par,  (n-1)^2  é ímpar, absurdo.
Seja n ímpar. Vamos tentar fazer com que a declaração acima sempre falhe, ou seja, elas sempre são iguais às casas (n-1)^2  restantes. Escolha uma casa aleatória e uma próxima a ela

o caso de  n ser par é trivial (não absurdo, IMO), porque as casas  (n-1)^2 restantes são um número ímpar, então você pode escolher qualquer casa, remover a linha / coluna e obter um número diferente de casas preto / branco nas casas restantes. Este é um resultado muito mais forte do que o que você precisa provar. Para  n impares, isso não funciona.

Então, vamos supor que  n  seja ímpar a partir de agora. Uma idéia possível nesse tipo de problema é considerar todos os cenários  n^2  diferentes (onde você seleciona uma casa e depois determina as casas restantes, conforme descrito no problema) 'ao mesmo tempo'.

Se tivermos um cenário em que o número de casas em preto e branco seja diferente, estaremos prontos. Caso contrário, isso significa que é o mesmo em cada cenário. Portanto, quando adicionamos o número de casas negras em cada cenário, obtemos o mesmo número S  que quando adicionamos o número de casas brancas em cada cenário.

OTOH, durante esse processo, contamos cada casa exatamente  (n-1)^2  vezes nesses cenários de  n^2  (não contamos se, no cenário especificado, selecionarmos uma casa na mesma linha ou coluna, que representa   2n-1  casos).

Mas isso significa que  S é (n-1)^2 vezes o número de casas brancas em todo o tabuleiro e  (n-1)^2  vezes o número de casas negras no tabuleiro, o que significa o número de casas negras no tabuleiro é igual ao número de casas brancas no tabuleiro.

Agora isso é impossível, já que  n  foi considerado ímpar, então as casas em preto e branco não podem ter o mesmo número.