Autor da análise: 
ctgPi
Resumo
Dadas as dimensões de um tabuleiro quadriculado $M \times N$, determine o número máximo de cavalos que podem ser colocados no tabuleiro sem que nenhum par de cavalos se ataque.
Solução
A idéia deste problema é bastante simples: se nós conseguirmos formar pares de quadrados a um movimento de cavalo de distância de tal forma que todas as casas (exceto uma, no caso de $M$ e $N$ ímpares) pertençam a exatamente um desses pares, podemos limitar superiormente o número de cavalos no tabuleiro a $\left\lceil \frac{MN}{2} \right\rceil$ usando o Princípio da Casa dos Pombos — os pombos são os cavalos e as casas são os pares de casas formados.
É óbvio que todo inteiro positivo $n \geq 3$ pode ser escrito em uma das formas $4k+3$, $4k+4$, $4k+5$, $4k+6$, onde $k \geq 0$. Logo, se provarmos que todos os tabuleiros cujas medidas dos lados pertencem a {3, 4, 5, 6} podem ser totalmente pareados, nós provamos que se $M \geq 3$ e $N \geq 3$ então a resposta do problema é $\left\lceil \frac{MN}{2} \right\rceil$ — basta colocar cavalos em todas as casas brancas.
Caso a menor dimensão (sem perda de generalidade $M$) seja 2, a resposta depende de $N \pmod 4$: basta preencher com cavalos todas as colunas cujos índices são congruentes a 1 ou 2 módulo 4. A demonstração de otimalidade usa novamente o PCP, ladrilhando o tabuleiro com sub-tabuleiros 2 × 4.
Finalmente, se $M = 1$, a resposta é obviamente $N$.
Construção dos pareamentos
2 × 4
| 1 | 3 | 2 | 4 |
| 2 | 4 | 1 | 3 |
3 × 3
| 1 | 2 | 4 |
| 3 | × | 1 |
| 2 | 4 | 3 |
3 × 4
| 3 | 5 | 1 | 6 |
| 1 | 4 | 3 | 2 |
| 5 | 2 | 6 | 4 |
3 × 5
| 1 | 3 | 2 | 6 | 7 |
| 2 | 4 | 7 | × | 5 |
| 3 | 1 | 5 | 4 | 6 |
3 × 6
| 3 | 5 | 2 | 7 | 9 | 8 |
| 2 | 6 | 1 | 5 | 4 | 7 |
| 1 | 3 | 4 | 6 | 8 | 9 |
4 × 4
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 2 | 1 | 4 | 3 |
| 6 | 5 | 8 | 7 |
4 × 5
| 3 | 5 | 6 | 4 |
| 6 | 4 | 3 | 5 |
| 7 | 1 | 2 | 8 |
| A | 8 | 7 | 9 |
| 1 | 9 | A | 2 |
5 × 5
| 2 | A | B | 6 | 3 |
| 5 | 6 | 2 | 7 | B |
| A | 1 | × | 3 | C |
| 9 | 5 | 4 | 8 | 7 |
| 1 | 8 | 9 | C | 4 |
6 × 5
| 2 | C | 6 | B | 3 |
| 5 | D | 7 | C | 6 |
| 7 | 2 | 5 | 3 | B |
| D | 1 | 8 | 4 | A |
| 8 | E | A | F | 9 |
| 1 | F | 9 | E | 4 |
Os tabuleiros 6 × 4 e 6 × 6 podem ser construídos com duas cópias dos tabuleiros 3 × 4 e 3 × 6, respectivamente.
Discuta o problema
Achei muito legal. Obter a resposta certa da idéia de formar pares chega a ser surpreendente, pois, com os pares, estamos considerando que cada casa pode ser atacada por apenas uma outra casa, quando na verdade poder ser atacada por mais. Então a impressão que dá é que o limitante obtido seria folgado, mas ele acaba dando a resposta certa.
Um outro argumento para verificar a resposta para o caso $M \geq 3$ e $N \geq 3$ segue das seguintes observações:
Então certamente podemos colocar cavalos em todos as casas de uma determinada cor, digamos branco. Assim já temos $\lceil \frac{MN}{2} \rceil$ cavalos. E se tentarmos colocar mais um cavalo ele ficaria em uma casa preta e portanto seria atacado. Ademais, não dá para ter mais do que $\lceil \frac{MN}{2} \rceil$ cavalos sem que todas as casas de uma determinada cor tenham cavalos.
Sim, ter a intuição de colocar todo mundo em casas de uma mesma cor é relativamente fácil, mas você ainda precisa formar os pares para fechar a demonstração — tanto que no caso $2 \times N$ a resposta não é $N$. Como um cavalo não ataca todas as casas da cor oposta, talvez existisse um arranjo que magicamente quebrasse o limite de 50% de densidade em alguma regiões pequenas, e aí nós poderíamos ladrilhar o tabuleiro com cópias dessa região menor.