PiR2
Gostaria de reagir a esta mensagem? Crie uma conta em poucos cliques ou inicie sessão para continuar.

Combinatória - Tabuleiro de xadrez

2 participantes

Ir para baixo

Combinatória - Tabuleiro de xadrez  Empty Combinatória - Tabuleiro de xadrez

Mensagem por Gabriel Rodrigues Qui 30 maio 2013, 20:25

De quantas formas podemos colocar 8 torres num tabuleiro de xadrez de modo que nenhuma torre possa "comer" outra?

Obs: Gostaria de uma resolução por Arranjo, se fosse possível. (já vi por combinação)

Gabriel Rodrigues
Matador
Matador

Mensagens : 1148
Data de inscrição : 08/02/2013
Idade : 28
Localização : São Carlos, SP

Ir para o topo Ir para baixo

Combinatória - Tabuleiro de xadrez  Empty Re: Combinatória - Tabuleiro de xadrez

Mensagem por JOAO [ITA] Dom 02 Jun 2013, 19:39

Observe o desenho que eu fiz:

Combinatória - Tabuleiro de xadrez  Xadrezx



Sabe-se, da teoria básica do Xadrez, que uma torre não pode capturar outra quando a outra não está na mesma vertical nem mesma horizontal que ela.

Vou enumerar as oito torres do problema por a, b, c, d, e, f, g e h.

Perceba que, inicialmente, podemos colocar 'a' em qualquer uma das 64 casas do tabuleiro.

Depois, podemos colocar 'b' em qualquer uma das 64 - 15 = 49 casas restantes (perceba que exclui as casas que estão na mesma vertical e horizontal de 'a'. Estas resultam em um total de 8 + 7 = 15 casas).

Depois, pode-se colocar 'c' em qualquer uma das 49 - 13 = 36 casas restantes (perceba que exclui as casas que estão na mesma vertical e horizontal de 'b'. Estas resultam um total de 7 + 6 = 13 casas).

...

Depois, pode-se colocar 'h' na única casa que sobrou.


Assim, o número total de modos de se distribuir essas torres pelo tabuleiro de modo que nenhuma delas fique na linha de ataque da outra é: 64.49.36.25.16.9.4.1 = 8!².

Mas, perceba que nessa análise eu considerei cada torre como uma entidade diferente que compartilha com as outras apenas o fato de atacar do mesmo modo.
Isso estaria correto se cada torre estivesse pintada de uma cor diferente, por exemplo.

Mas como isso não ocorre (ou seja, todas as torres são iguais), deve-se dividir o resultado pelo total de permutações presentes no conjunto de torres {a,b,c,d,e,f,g,h}, pois a ordenação (a,b,c,d,e,f,g,h) é igual a ordenação (h,g,f,e,d,c,b,a) e a todas as outras permutações de (a,b,c,d,e,f,g,h).
Ora, esse total de permutações pode ser encontrado facilmente: P = 8!

Assim, o total de maneiras de dispor oito torres num tabuleiro de xadrez de modo que nenhuma torre possa atacar a outra é:
8!²/8! = 8! maneiras.


JOAO [ITA]
JOAO [ITA]
Fera
Fera

Mensagens : 866
Data de inscrição : 25/02/2012
Idade : 27
Localização : São José dos Campos,SP,Brasil

Ir para o topo Ir para baixo

Combinatória - Tabuleiro de xadrez  Empty Re: Combinatória - Tabuleiro de xadrez

Mensagem por Gabriel Rodrigues Dom 02 Jun 2013, 20:39

Boa resolução, João!

Mas, segundo seu raciocínio, dê um exemplo de duas permutações distintas.

Gabriel Rodrigues
Matador
Matador

Mensagens : 1148
Data de inscrição : 08/02/2013
Idade : 28
Localização : São Carlos, SP

Ir para o topo Ir para baixo

Combinatória - Tabuleiro de xadrez  Empty Re: Combinatória - Tabuleiro de xadrez

Mensagem por JOAO [ITA] Dom 02 Jun 2013, 21:35

Vou desenhar duas permutações distintas:

Combinatória - Tabuleiro de xadrez  Permutao1



Combinatória - Tabuleiro de xadrez  Permutao2



JOAO [ITA]
JOAO [ITA]
Fera
Fera

Mensagens : 866
Data de inscrição : 25/02/2012
Idade : 27
Localização : São José dos Campos,SP,Brasil

Ir para o topo Ir para baixo

Combinatória - Tabuleiro de xadrez  Empty Re: Combinatória - Tabuleiro de xadrez

Mensagem por Gabriel Rodrigues Seg 03 Jun 2013, 09:19

Tudo bem, entendi!

Um outro jeito de fazer seria considerar todas as torres em linhas diferentes por permutação (como seu primeiro desenho). Dessa forma, não haveria repetições.
Considerando isto como hipótese, só teríamos que deixá-las em colunas diferentes, o que poderia ser feito de 8! formas.

Valeu a ajuda cheers

Gabriel Rodrigues
Matador
Matador

Mensagens : 1148
Data de inscrição : 08/02/2013
Idade : 28
Localização : São Carlos, SP

Ir para o topo Ir para baixo

Combinatória - Tabuleiro de xadrez  Empty Re: Combinatória - Tabuleiro de xadrez

Mensagem por Conteúdo patrocinado


Conteúdo patrocinado


Ir para o topo Ir para baixo

Ir para o topo

- Tópicos semelhantes

 
Permissões neste sub-fórum
Não podes responder a tópicos