Questão de tabuleiro

De quantos modos podemos colocar 5 reis em casas não adjacentes em um tabuleiro 8 por 8?

Fernanda:

Vou transcrever uma solução dada pelo Prof. Paulo C.P. Carvalho PhD em Pesquisa Operacional Pela Universidade Cornell.

O tabuleiro de 64 casas possui 4 casas de canto (vértices), 24 casas laterais que não são vértices e 36 casas centrais.Cada casa de canto possui 3 casas adjacentes; cada lateral possui 5 casas adjacentes e cada central possui 8 casas adjacentes.Vamos contar separadamente os casos que ocorrem conforme o rei negro ocupe
uma casa de canto, lateral ou central.Se o rei negro ocupar uma casa de canto, haverá 4 posições para o rei negro e 60 posições para o rei branco, pois das 64 casas do tabuleiro uma estará ocupada e as 3 a ela adjacentes não poderão ser ocupadas pelo rei branco.Haverá portanto 4 × 60 = 240 modos de dispor os reis.

Se o rei negro ocupar uma casa lateral que não seja de canto, haverá 24 posições para o rei negro e 58 posições para o rei branco, pois das 64 casas do tabuleiro uma estará ocupada e as 5 a ela adjacentes não poderão ser ocupadas pelo rei branco. Haverá portanto 24 × 58 = 1.392 modos de dispor os reis.

Se o rei negro ocupar uma casa central, haverá 36 posições para o rei negro e 55 posições para o rei branco, pois das 64 casas do tabuleiro uma estará ocupada e as 8 a ela adjacentes não poderão ser ocupadas pelo rei branco. Haverão portanto 36 × 55 = 1.980 modos de dispor os reis.

Portanto, a resposta é 240+1.392+1.980 = 3.612. Se os reis fossem iguais, a resposta seria a metade da resposta anterior, 1.806.

Para 5 reis, o pensamento é análogo.

Abraços,
Pedro

Eu tentei entender mas sinceramente não consegui, a questão dessa resposta é um pouco diferente pois são dois reis e eu não entendi pois parece que está contando duas vezes as casas adjacentes .
Mesmo assim obrigada.

A questão da sua resposta é :De quantos modos podemos colocar 2 reis diferentes em casas não adjacentes de um tabuleiro 8x8  ? E se os reis fossem iguais ?


Eu entendi a respsota , divide por 2 se  fossem diferentes pois está contando duas vezes as adjacentes mas para 5 reis , eu teria que fazer como ? Dividir por 5 ou por 10 ??? 

Bom, Fernanda, como o enunciado não cita se os reis são iguais ou não, você pode considerar que todos são diferentes.

Mas se os 5 fossem diferentes eu teria que ver todas as possibilidades , como são 2 eu fixo um e vou fazendo o que não pode para o outro mas com 5 são muitas possibilidades...
Eu não sei como ficaria ..

Fernanda, não tenho certeza, mas acho que você pode fazer da seguinte maneira:

Faça para dois reis. Depois, a partir das posições disponíveis para o segundo rei, faça para o terceiro e assim por diante.

Alguém pode nos ajudar?

Olá pessoal.

O tabuleiro pode ser representado com anagramas, onde P significa rei preto e B rei branco e V, casa vazia.
Então, há 64 letras nessa palavra, BPVVV...
Fazendo como anagrama, há 64!/62! formas possíveis de anagramas.
64*63=4032
Tabuleiro:
  1 2 3 4...
A
B
C
.
.
.

Agora vamos imaginar só a forma de preencher a primeira linha, com o rei P e B sendo adjacentes.
PBVVVVVV, VPBVVVVV...

Nessa situação, as casas restantes do tabuleiro, sempre ficam vazias.
Existem evidentemente, 7 possibilidades de manter o PB juntos nessa linha, porém, PB é diferente de BP nesse caso, P e B podem ser permutados de 2! maneiras. Então para cada possibilidade, há 2! maneiras na verdade, então fica 7*2!=14

Agora, podemos seguir a mesma ideia, para todas as linhas e colunas existentes, como são 16, fica 16*14=224.

Porém, há as "adjências" das diagonais.
Agora, há a possibilidade da diagonal principal, permuta-se de modo que o B e P sempre fiquem juntos como antes. Como são 8 casas, o valor é o mesmo do anterior:
7*2!=14, mas existe a diagonal principal e a secundária para se considerar,
então são 14*2=28.

Agora, vamos considerar cada diagonal à direita da secundária.
São 7 casas, e aí elas vão diminuindo e diminuindo, até 1.
Precisamos permutar o P e o B em cada uma dessas diagonais e imaginá-los juntos.
Primeiro temos 6 opções (7 casas),5 opções (6 casas)...4,3,2, 1 (2 casas).
A casa que sobra, não se conta, pois ela já é uma maneira da diagonal principal.

Porém, lembrando que há sempre 2! maneiras para cada opção, então fica:

2!*(6+5+4+3+2+1)=42

Agora, há outras diagonais, para cada diagonal (exceto as 2 com 8 casas), há na realidade mais três.

Então há na realidade 4 vezes maneiras possíveis.

42*4=168

Pronto, fizemos todas as possíveis adjacências, não poderemos supor qualquer opção de "adjência" que não cairá numa dessas possibilidades que imaginamos.

Mas, o problema pediu somente as possibilidades de não-adjacentes.

Relembrando, há 4032 maneiras possíveis para se espalhar os reis no tabuleiro, há 224 considerando as linhas e colunas, há 28 nas diagonais maiores e 168 nas menores.

224+28+168=420

4032-420=3612 maneiras em que os reis não são adjacentes.

Se os reis fossem iguais, vimos que consideramos cada opção
como diferente para cada permutação, então PB é diferente de BP, no caso deles sendo iguais, PB=BP, então contamos tudo dobrado, aí bastaria dividir por 2.

Para 3 reis, ABC=CBA=BCA...
Há 6 opções no total que é a permutação de 3 elementos.
Para 5, seria dividir por 5!.

Estou meio perdido para entender a questão dos 5 reis, pois não sei se 4 reis juntos e 1 separado seria adjacente ou se a questão quer todos os reis separados, Fernanda, você teria a resposta da questão por gentileza?