Questão 9. Num tabuleiro de xadrez, formado por 8 linhas e 8 colunas, devemos escolher 8 casas, de modo que não há duas delas na mesma linha, nem na mesma coluna. Além disso, nenhuma das 4 casas dos cantos do tabuleiro pode ser escolhida. De quantas maneiras podemos escolher essas 8 casas?
A ( ) 11520
B ( ) 15120
C ( ) 18720
D ( ) 20160
E ( ) 21600
A ( ) 11520
B ( ) 15120
C ( ) 18720
D ( ) 20160
E ( ) 21600
Passo 1
Vou escrever claramente o que o enunciado dá e o que pede, com todos os dados explicitados.
- O tabuleiro tem
linhas e colunas, ou seja, é um tabuleiro de . - Devemos escolher
casas de modo que não haja duas escolhidas na mesma linha nem na mesma coluna. - Além disso, nenhuma das
casas dos cantos pode ser escolhida (os cantos são se numerarmos linhas e colunas de a ). - A pergunta: de quantas maneiras podemos fazer essa escolha que satisfaz todas as restrições?
Passo 2
Entendendo a modelagem do problema (sem pular etapas).
- A condição “não há duas na mesma linha nem na mesma coluna” significa que em cada linha escolhemos exatamente uma casa e, simultaneamente, cada coluna contém exatamente uma das casas escolhidas. Isso é exatamente o mesmo que escolher uma permutação de
elementos: para cada linha escolhemos a coluna , onde é uma bijeção de em si mesma. - Portanto, contar escolhas válidas é contar permutações
de sujeitas à restrição de que não coloque nenhum dos quatro pares proibidos .
Explicando conceito básico usado:
- O número total de permutações de
elementos sem restrição é . Aqui (fatorial) significa produto dos inteiros positivos até o número: . Calculando, .
Passo 3
Defino os eventos “permutações que usam uma posição proibida” para aplicar inclusão-exclusão.
- Seja
o conjunto de permutações com (ou seja, que usam a casa ). - Seja
o conjunto de permutações com (casa ). - Seja
o conjunto de permutações com (casa ). - Seja
o conjunto de permutações com (casa ).
Queremos contar permutações que não pertencem a nenhum de
. A ferramenta apropriada é o princípio da inclusão-exclusão.
Passo 4
Lembrete do princípio da inclusão-exclusão (explicado de forma didática).
- Se
é o conjunto total de permutações, então o número de permutações que evitam todas as posições proibidas é
- A ideia: subtrai-se as permutações que violam pelo menos uma restrição, mas como as interseções foram subtraídas várias vezes, reverte-se adicionando as interseções de pares, etc.
Passo 5
Calculo dos tamanhos das interseções simples (eventos individuais).
- Se
(evento ), então o resto é qualquer permutação das colunas restantes entre as linhas restantes. Logo
- O mesmo vale para
, cada um fixa uma posição e deixa permutações do resto, então
- Como são
eventos simples, a soma é
Para referência numérica,
, então
.
Passo 6
Calculo das interseções de dois eventos.
- Algumas interseções são impossíveis por causa da condição de permutação (uma linha só pode mapear para uma coluna e uma coluna só pode receber uma linha). Vou examinar todos os tipos:
- Interseções que fixam duas imagens da mesma linha, por exemplo
( e ) são impossíveis. Logo e . - Interseções que fixam a mesma coluna para duas linhas, por exemplo
( e ) também são impossíveis, porque a coluna não pode ser atribuída a duas linhas. Assim e . - As interseções que restam são:
-
: e . Essas duas posições são compatíveis (linhas e colunas diferentes), então fixando essas duas pares restam linhas e colunas para permutar livremente. Logo
-
: e . Também compatível, e igualmente
-
- Interseções que fixam duas imagens da mesma linha, por exemplo
- Todas as outras interseções de pares são vazias. Portanto a soma sobre pares é
Numericamente,
, então
.
Passo 7
Interseções de três ou quatro eventos.
- Qualquer interseção que envolva três eventos é impossível aqui. Por exemplo, tentar ter
, e é impossível já porque não pode ter dois valores; combinando os tipos possíveis não se consegue fixar três imagens sem violar a bijetividade. Uma verificação rápida mostra que todas as interseções de três são vazias. - A interseção de todos os quatro eventos também é vazia, pois implicaria contraditórios (
com dois valores ou uma coluna com duas linhas).
Logo todas as somas de interseções de ordem
ou
valem
.
Passo 8
Aplicando inclusão-exclusão e fazendo as contas finais.
- Usando a fórmula e os valores obtidos:
- Substituindo os valores numéricos:
- Portanto
Passo 9
Interpretação final e checagem rápida.
- O valor obtido é
. Faz sentido: sem restrição de cantos seriam permutações; proibir quatro posições reduz bastante o total, mas ainda sobra uma quantidade grande. - Conferência de plausibilidade: o resultado é um inteiro e aparece entre as alternativas (E).
Resposta
21600