De quantos modos é possível colocar 8 torres brancas em um tabuleiro de xadrez 8 times 8 de modo que nenhuma torre fique na diagonal branca e não haja duas torres na mesma linha ou na mesma coluna?

Passo 1

O enunciado pede para colocar 8 torres em um tabuleiro 8times8 de forma que não haja duas torres na mesma linha nem na mesma coluna (situação de permutação de colunas em cada linha) e, além disso, nenhuma torre esteja na diagonal branca que liga a8 a h1. Essa diagonal branca é dada pelos quadrados de coordenadas (i,9-i), para i=1,2,dots,8. O conteúdo principal que vamos usar é o princípio da inclusão–exclusão aplicado a permutações com posições proibidas.

Passo 2

Modelamos cada disposição de torres por uma permutação piin S8, onde pi(i) é a coluna escolhida na linha i. A condição “nenhuma torre na diagonal branca” equivale a
pi(i)neq 9 - i para todo i=1,dots,8
Chamemos de Ai o conjunto de permutações com pi(i)=9-i. Queremos contar
l|capi=1^8 Ai^cr| =l|pi:pi(i)neq9-i forall ir|

Passo 3

Pelo princípio da inclusão–exclusão,
l|capi=1^8 Ai^cr| =sumk=0^8(-1)^k sumIsubset1,dots,8,,|I|=k l|capiin IAir|
Se fixamos k condições pi(i)=9-i, resta permutar as outras 8-k linhas livremente, dando (8-k)! permutações. Há binom8k escolhas de I. Logo
l|capi=1^8 Ai^cr| =sumk=0^8(-1)^kbinom8k(8-k)!

Passo 4

Calculamos termo a termo:
k=0:& binom808! = 1cdot40320 = 40320, k=1:& -binom817! = -8cdot5040 = -40320, k=2:& binom826! = 28cdot720 = 20160, k=3:& -binom835! = -56cdot120 = -6720, k=4:& binom844! = 70cdot24 = 1680, k=5:& -binom853! = -56cdot6 = -336, k=6:& binom862! = 28cdot2 = 56, k=7:& -binom871! = -8cdot1 = -8, k=8:& binom880! = 1cdot1 = 1
Somando tudo:
40320-40320+20160-6720+1680-336+56-8+1 = 14833

Resposta

14833 modos.

Exercícios de Livros Relacionados