Embaralhar pra quê?

Nesse post, vamos falar sobre embaralhar um grupo de objetos (por exemplo, cartas). Nesse contexto, embaralhar um grupo de objetos é trocar a ordem desses objetos. Mais especificamente, vou tentar mostrar que, qualquer que seja o procedimento adotado para embaralhar, se esse procedimento for repetido diversas vezes de forma igual, depois de algum tempo os objetos retornam à posição original.

Veja que estamos sendo bastante ambiciosos: nada foi dito a respeito da natureza desses objetos ou da natureza do procedimento de embaralhar. Só estamos exigindo que embaralhar seja trocar a ordem e que o embaralhemento seja repetido de forma idêntica.

Eu sinto muito, mas vai ser útil usar um pouco de formalismo matemático para a "prova". Primeiro, vamos combinar algumas coisas:

[1] G representa um grupo de N objetos numerados de 1 a N (sem ninguém ter o mesmo número, claro). Dizer portanto "objeto x" é dizer "objeto que tem a numeração x" ou ainda "objeto que ocupa a posição x".

[2] E representa um embaralhamento (isso existe?) que muda a numeração de cada objeto de G.

[3] E(x) corresponde à nova numeração que o objeto x passa a ter após G ser embaralhado. Assim, dizer que "E(5) = 7" é o mesmo que dizer "o quinto objeto passa a ser o sétimo".

Deseja-se provar, portanto, que aplicar E a G diversas vezes acaba fazendo cada objeto de G voltar à numeração (ou posição) original.

Para preparar terreno, é importante fazer uma observação que vai ser útil no fim das contas: dois objetos não podem nunca ter o mesmo número - ou ocupar a mesma posição (afinal, eles estão ordenados). Em outras palavras,

"Não existem dois números distintos x,y tais que

G(x) = G(y)"

Lembre-se disso! Essa afirmação é tão natural quanto a que diz "se o quinto objeto passa a ser o sétimo, nenhum outro passa a ser o sétimo também".

-------------------------------------------------------------

Primeiros vamos provar algo mais fraco, que será nosso lema:

"Se cada objeto volta à posição original em algum momento, existe um momento em que todos eles ocupam a posição original ao mesmo tempo".

Ora, seja Ori(x) o número de vezes que devemos aplicar E a G para que o objeto x volte à posição original. Pela hipótese ("... cada objeto volta à posição original em algum momento"), todo objeto x tem um Ori(x).

Também é fácil ver que aplicar E a G qualquer múltiplo de Ori(x) também faz o objeto x retornar à posição original. Por exemplo: se o quinto objeto volta a ser o quinto objeto após 7 embaralhamentos, é claro que após 21 embaralhamentos o quinto objeto também volta a ser o quinto objeto, pois 21 = 3x7.

Agora aplique E a G um número de vezes igual a Ori(1)*Ori(2)*...*Ori(N), lembrando que '*' é o símbolo da múltiplicação. Esse número é múltiplo de Ori(x), qualquer que seja x entre 1 e N. Então após esse número de embaralhamentos cada objeto retornará à posição original.

--------------------------------------------------------------

Agora, à prova!

Ela será dada por absurdo, ou seja, suporemos que a nossa afirmação é falsa e chegaremos a algo absurdo. Assim, provaremos que a nossa afirmação é verdadeira.

Por absurdo, suponha que G nunca volta ao estado original. Então, pelo que provamos acima, existe um objeto k que nunca volta à posição original. Afinal, se todos voltassem, menos que em momentos distintos, provamos que em algum momento todos voltariam.

Após N aplicações de E a G - ou "após N embaralhamentos" - o objeto, originalmente o objeto k, passa por N+1 posições possíveis. Como ele nunca volta à posição k, ele em algum momento voltou a um lugar (diferente de k) que já tinha ocupado antes. O que está ocorrendo é, por exemplo, o seguinte...

Suponnha que o objeto 8 nunca volta à posição original:

Então podemos ter algo como...

E(8) = 7 ; E(7) = 5 ; ... ; E(11) = 3 ; ... ; E(4) = 11.

Veja que 11 já tinha sido ocupado antes. O objeto então fica indo da posição 11 até a posição 4, passando (talvez) por alguns números nesse processo, e depois volta para a 11. É como se ele ficasse num 'loop' que não inclui sua posição original, o 8.

Calma, que tá acabando! Bem, agora sabemos que o objeto (originalmente k) está num loop que não inclui a posição k. Ora, mas ele em algum momento esteve fora desse loop, porque em algum momento ele esteve na posição k. Assim, existiu um momento em que ele estava fora do loop e, depois de um embaralhamento, ficou dentro do loop. Traduzindo, existe uma posição p tal que:

[1] a posição p não está no loop

[2] E(p) é uma posição que está no loop

Vamos dizer que E(p) = y. No loop, por definição de loop, existe também uma posição, vamos dizer z, tal que E(z) = y. Como p não está no loop e z está, p e z são distintos, mas E(p) = E(z). Isso é um absurdo, pois dois objetos distintos não podem ocupar a mesma posição após um embaralhamento. Daí, não existe objeto que nunca volte à posição original. Pelo nosso lema, existe um momento que todos os objetos voltam à posição original.

Fim da prova.