15/07/2023

Solução para o desafio: Dominós e xadrez

A apresentação do desafio "Dominós e xadrez" está neste link.

Prometi apresentar a solução "um mês (ou dois, ou três...)" e demorei 17 meses! Desculpem-me!

Mas, enfim, vamos à solução.

Relembrando de alguns detalhes e já evoluindo na análise do desafio:

O tabuleiro de xadrez tem 64 casas, sendo, 32 casas brancas e 32 casas pretas.


A B C D E F G H
8 A8 B8 C8 D8 E8 F8 G8 H8 8
7 A7 B7 C7 D7 E7 F7 G7 H7 7
6 A6 B6 C6 D6 E6 F6 G6 H6 6
5 A5 B5 C5 D5 E5 F5 G5 H5 5
4 A4 B4 C4 D4 E4 F4 G4 H4 4
3 A3 B3 C3 D3 E3 F3 G3 H3 3
2 A2 B2 C2 D2 E2 F2 G2 H2 2
1 A1 B1 C1 D1 E1 F1 G1 H1 1

A B C D E F G H

E pode ser completamente coberto com 32 peças de dominó, como no exemplo abaixo:


A B C D E F G H
8




8
7




7
6



6
5


5
4



4
3



3
2



2
1


1

A B C D E F G H

--

Lembrando a regra "Cada peça de dominó deve ser posicionada na horizontal ou na vertical... cobrindo sempre 2 casas tabuleiro de xadrez...".

Observando o tabuleiro, chegamos a seguinte premissa:

  • Uma peça de dominó sempre cobrirá 2 casas de cores diferentes.
    • Isso porque casas vizinhas no tabuleiro, vertical ou horizontalmente, sempre apresentam cores diferentes.

Assim, "se você ocupar duas casas quaisquer do tabuleiro de xadrez, com um peão em cada uma", podemos chegar a conclusão que, para termos possibilidade de cobrir as demais casas com peças de dominó:

  • Cada uma das casas ocupadas com peões tem que ser de uma cor diferente.
    • Pois, deste forma, ficam livres o mesmo número de casas brancas e pretas.

Com isso já sabemos que a resposta não é 100%, para a pergunta "... qual é a probabilidade de você conseguir cobrir todas as casas restantes...?".

Aqui o problema está parcialmente resolvido: Se os dois peões forem colocados em casas da mesma cor, não conseguiremos cobrir o tabuleiro com peças de dominó.

Porém, ainda não sabemos "... a probabilidade de você conseguir cobrir todas as casas restantes...", caso os dois peões estejam em casas de cores diferentes.

--

Um caminho para a solução é se afundar em cálculos complexos que tentem cobrir todas as probabilidades de arrumação das peças de dominó, para todas as possíveis posições dos peões.

Mas, ainda bem, existe uma forma mais fácil de resolver o problema.

A ideia para a solução parte do seguinte questionamento: E se partimos de um tabuleiro já coberto de peças de dominó e abrirmos espaço para os dois peões?

Se tirarmos uma peça de dominó, já temos uma solução: a de colocar os peões em duas casas vizinhas.

Mas, e todas as outras combinações de duas casas de cores diferentes não vizinhas?

Para esses casos, além de tirar uma peça de dominó, que está cobrindo a primeira casa escolhida, será necessário reorganizar várias outras peças de dominó, até liberarmos mais uma casa, de cor diferente da primeira liberada.

E temos que conseguir fazer isso para todas as casas de cor diferente.

Essa rearrumação parece caótica e muito difícil de analisar se será possível liberar qualquer uma das 32 casas de cor diferente da primeira casa liberada.

Mas, se se fizermos uma arrumação pensada para facilitar essa reorganização?

Obs.: Esse, para mim, é o pulo do gato dessa abordagem. É o momento em que um problema se torna um prazer.

Se arrumarmos as peças de dominó como vagões de um trem, seguindo um circuito fechado, que passe por todas as casas do tabuleiro. Desta forma, ao mover qualquer peça, seguindo o circuito, todos os movimentos a seguir serão ordenados e previsíveis, não caóticos.

Um exemplo de circuito fechado para as peças:


 

 

 

 

 

 

 

 

 

Posicionando as peças no circuito, iniciando na casa A8 e terminando na casa A7:












Show!

Mas será que podemos andar com esse "trem de peças de dominó" no circuito?

Agora posicionando as peças no circuito, iniciando na casa B8, que era a segunda casa da disposição apresentada acima, e terminando na casa A8:


 










Perfeito!

Assim, qualquer casa que eu escolha para o primeiro pião, eu consigo colocar o segundo pião em qualquer casa de cor diferente da primeira, movendo peças de dominó seguindo o circuito imaginário do nosso "trem de peças".

Seguem exemplos para melhor visualizar essa conclusão.

Digamos seja escolhida para o primeiro pião a casa C4, que é branca.

Se for escolhida para o segundo pião a casa preta C3, basta retirar uma peça de dominó:











Se for escolhida para o segundo pião a casa preta G7, tenho que mover as peças entre essa duas casas seguindo o circuito imaginado:


 










Só mais um exemplo. Se for escolhida para o segundo pião a casa preta A1, da mesma forma, tenho que reorganizar as peças seguindo o circuito imaginado:


 

 

 

 

 

 

 

 

 

 

--

Assim a podemos complementar a solução parcial apresentada anteriormente, ficando assim: Se os dois peões forem colocados em casas da mesma cor, não conseguiremos cobrir o tabuleiro com peças de dominó, e se forem colocados em casas de cores diferentes, conseguiremos cobrir o tabuleiro com peças de dominó.

Ou seja, ao colocarmos o primeiro peão em uma posição aleatória, das 64 possíveis casas do tabuleiro, o segundo peão deve ser colocado em uma da 32 casas de cor diferente da casa do primeiro peão. Lembrando que este só teria 63 casas disponíveis.

Se a escolha da casa do segundo peão também for aleatória, como pede o desafio, temos uma chance de 32/63 de ser uma casa que permita que todas as demais casas sejam cobertas com peças de dominó.

32/63 = 0.507936508

Arredondando: 50,8%

Assim, "se você ocupar duas casas quaisquer do tabuleiro de xadrez, com um peão em cada uma", "a probabilidade de você conseguir cobrir todas as casas restantes do tabuleiro de xadrez com peças de dominó" é de 50,8%

Como avise antes, a quantidade de cálculos necessária foi mínima.

A solução se baseia quase somente em observação e entendimento das variáveis do problema.

Eu curti muito a solução desse desafio. Tanto que me dei ao trabalho de compartilhar.

Espero que tenham gostado.

--

Links:

- The ARCTIC CIRCLE THEOREM or Why do physicists play dominoes?

    Foi dos primeiros 7 minutos desse vídeo que busquei inspiração para montar este desafio.

    Esse vídeo faz parte do canal Mathologer, que recomendo a todos que gostem de matemática e de suas mais loucas aplicações e consequências.

 

Nenhum comentário:

Postar um comentário