Exercício 1.2.10. De quantas maneiras distintas podemos colocar num tabuleiro de xadrez um rei branco e um preto de modo que um não ataque o outro?
Passo 1
Estamos no tema de contagem de configurações em um tabuleiro de xadrez
. Precisamos contar de quantas formas podemos colocar um rei branco e um rei preto em casas distintas de modo que eles não se ataquem, ou seja, que a distância de Chebyshev entre eles seja pelo menos 2.
Passo 2
Primeiro calculamos o número total de colocações sem restrição. Como temos
casas e os reis são distinguíveis (branco e preto), escolhemos uma casa para o rei branco e outra para o rei preto:
Passo 3
Agora contamos quantas dessas posições são ilegais, ou seja, em que os reis se atacam. Um rei ataca todas as casas adjacentes (horizontal, vertical ou diagonal), até 8 casas por posição. Para cada casa onde colocamos o rei branco, o número de casas que o rei preto não pode ocupar é igual ao grau dessa casa no grafo de adjacência.
Passo 4
Classificamos as casas e somamos seus graus:
Logo,
Esse é o total de posições ilegais (contadas em ordem: rei branco primeiro, depois rei preto).
Passo 5
O número de colocações válidas é