OBM 2017 - Nível 2 - P3

Problema 3.

Seja $n>1$ um inteiro e considere um tabuleiro $n\times n$, em que algumas das $n^2$ casas foram pintadas de preto, e as restantes foram pintadas de branco. Prove que é possível escolhermos uma das $n^2$ 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)^2$ casas restantes.

Solução:

Primeiramente, divida o problema em dois casos;
Caso 1: Se $n$ for par
Note que $(n-1)^2$ será um número ímpar e consequentemente não podemos ter o números de casas brancas igual ao de casas pretas.
Caso 2: Se $n$ for ímpar
Denote por $x_1$ e $x_2$ a quantidade inicial de casas brancas e pretas, respectivamente. Assuma, sem perdas, que $x_1>x_2$, provaremos que existe uma casa que, após aplicarmos a operação(remoção), haverá mais casas brancas do que pretas.
Para cada $1\leq i,j\leq n$, defina $h(i,j)$ como sendo o número de casas brancas obtidas após a remoção da linha $i$ e coluna $j$. Assim, teremos que:
$\sum_{1\leq i,j\leq n} h(i,j) =(n-1)^2x_1$, pois no somatório, cada casa branca no tabuleiro está sendo contada $(n-1)^2$ vezes. Portanto, temos que:
$\sum_{1\leq i,j\leq n} h(i,j) =(n-1)^2x_1>\frac{(n-1)^2n^2}{2}$ e como o somátorio possui $n^2$ inteiros não-negativos, pelo Princípio das Casas dos Pombos(PCP), há algum par $(i,j)$, tal que $h(i,j)\geq \frac{(n-1)^2}{2}+1$, logo o resultado segue.