Math Puzzle: The longest shuffle

Desafio matemático revela qual é a sequência de embaralhamento mais longa

Tecnologia

Se você embaralhar repetidamente um baralho de 10 cartas usando exatamente o mesmo método, qual é o maior número de embaralhamentos que você poderia precisar antes que o baralho retorne à sua ordem original?

Por exemplo, um embaralhamento bobo pode simplesmente envolver a troca das cartas superior e inferior, deixando o restante intocado. Após apenas duas aplicações desse embaralhamento, o baralho é restaurado. E quanto a embaralhamentos mais complicados? Nota: os embaralhamentos são baseados apenas nas posições das cartas, não na carta específica. Por exemplo, você pode dizer: “Always move the top card down four positions,” mas você não pode dizer: “Always move the queen of spades down four positions.”

O segredo por trás dos ciclos

Será necessário um máximo de 30 embaralhamentos antes que o baralho retorne à sua ordem original.

Cada embaralhamento, não importa quão complicado seja, mapeia em última análise cada posição no baralho para outra posição, ou seja, um embaralhamento é alguma permutação do baralho. As permutações sempre podem ser decompostas em ciclos discretos. Para entender isso, considere o exemplo de embaralhamento dado abaixo, onde a carta superior acaba na sexta posição, a segunda carta vai para o topo, e assim por diante.

Siga a carta que começa no topo. O primeiro embaralhamento a move para a posição seis, o segundo a move da posição seis para a posição nove, o terceiro para a posição dois e o quarto de volta para a posição um. Então ela viaja ao redor de um ciclo de quatro posições: um → seis → nove → dois → um. Note que as cartas que começam nas posições dois, seis e nove também viajam ao longo desse mesmo ciclo antes de retornar às suas posições originais. Seguindo as outras cartas, você descobrirá que este embaralhamento pode ser decomposto em ciclos de comprimentos quatro, três, dois e um. Cada carta pertence a algum ciclo, e nenhuma carta pertence a dois ciclos diferentes. (Cada posição aponta para outra posição e é apontada por outra posição. Para participar de dois ciclos, uma posição teria que apontar para dois lugares diferentes ou ser apontada por dois lugares diferentes.)

Cada embaralhamento pode ser decomposto desta maneira. O comprimento de um ciclo representa o número de cartas nesse ciclo, de modo que os comprimentos sempre somam 10. Por exemplo, o embaralhamento que simplesmente pega a carta superior e a coloca na parte inferior criaria um grande ciclo de comprimento 10. O “embaralhamento” vácuo que se recusa a mover quaisquer cartas se decompõe em 10 “ciclos”, cada um de comprimento um.

Uma carta em um ciclo de comprimento três retorna à sua posição inicial após três embaralhamentos e depois novamente após seis, nove, 12, e assim por diante. Assim, todo o baralho está de volta em ordem na primeira vez que cada ciclo tiver completado um número inteiro de voltas. Esse é o mínimo múltiplo comum dos comprimentos dos ciclos. Para fazer o baralho demorar o máximo possível para retornar, queremos dividir 10 em comprimentos de ciclo com o maior múltiplo comum mínimo possível.

Encontrando a combinação perfeita

Ciclos cujos comprimentos compartilham um fator comum desperdiçam cartas. Ciclos de quatro e seis, por exemplo, estão ambos de volta ao lugar após 12 embaralhamentos, mas ciclos de quatro e três também estão, e eles deixam você com três cartas adicionais para jogar. Portanto, as melhores opções usam comprimentos sem fatores comuns. O vencedor é 5 + 3 + 2 = 10, o que leva 5 × 3 × 2 = 30 embaralhamentos.

Fato curioso: para um baralho completo de 52 cartas, o embaralhamento mais longo usa ciclos de comprimento quatro, cinco, sete, nove, 11 e 13, além de três cartas que permanecem em suas posições originais, e são necessários 180.180 embaralhamentos para restaurar o baralho.

What do you feel about this post?

0%
like

Like

0%
love

Love

0%
happy

Happy

0%
haha

Haha

0%
sad

Sad

0%
angry

Angry

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *