Jaime Poniachik
Buenos Aires, Argentina

Um maço de cartas é um agradável kit para jogos matemáticos. É bom lembrar que os jogos são, antes de tudo, um mero entretenimento; mas, uma vez estando envolvidos pelo desafio, podemos continuar com assuntos mais sérios. Vejamos:
 

Vamos usar nove cartas de um naipe: de 1 (A - ás) até o 9. Embaralhe as cartas e segure-as na mão, abertas em leque, com todos os números à vista. O objetivo é levar as cartas para a sua ordem natural de 1 a 9.

Movimento: tome um conjunto de n cartas, começando com uma carta de número n seguida das cartas vizinhas à esquerda. Leve esse conjunto de cartas, sem desordená-lo, para a esquerda, passando por quantos espaços você quiser, e encaixe-o no ponto escolhido.
No exemplo, a partir da carta de número 3, tomamos três cartas, para deslocar para outro lugar da seqüência.
 

Sua vez: Embaralhe as cartas e tente resolver o problema sozinho. Talvez você consiga uma disposição inicial que facilite o trabalho, ou não. De qualquer modo, em geral, você deve conseguir chegar à solução, a não ser que comece com uma disposição muito azarada.

Magia? No final do artigo forneceremos uma explicação.
 

Vamos estabelecer uma nova regra, usando, de novo, as cartas de valores consecutivos de 1 a 9. Embaralhamos o pacote e seguramos também em leque como antes. Com o mesmo objetivo de levar as cartas à sua ordem natural, tome um par qualquer de cartas vizinhas e leve-o, sem alterar a ordem do par, para algum outro lugar, sempre fazendo os movimentos para a esquerda.

No exemplo, mostramos como se passou da ordem 54321 para 12345, com apenas três movimentos.

Tente agora com seis cartas. Embaralhe o pacote e proponha-se a colocar as cartas na ordem natural.

Às vezes a tarefa será fácil, outras vezes será difícil, ... e às vezes mais que difícil. Um caso duro é passar da ordem 654321 para 123456. Será que é possível fazê-lo? Há alguma maneira de saber, apenas observando a disposição inicial, se o problema tem solução? Se é fácil ou difícil?
 

O movimento é análogo ao anterior, levando três cartas de cada vez, no lugar de duas. Tome seis cartas com os números de 1 a 6, embaralhe-as e tente levá-las à ordem natural movimentando três cartas quaisquer para a esquerda. A figura mostra uma seqüência de movimentos desse tipo.

Cabe perguntar, como fizemos no caso anterior, se todas as ordens estão conectadas, isto é, se dada uma ordem qualquer das cartas, será possível levá-las para uma outra ordem desejada.

Um desafio adicional é buscar a solução que usa o menor número possível de movimentos. Pudemos experimentar, sozinhos e com amigos a quem propusemos o jogo, que em muitos casos é fácil perder-se e começar a mover as cartas de um lado para outro sem chegar ao resultado desejado. Quando finalmente descobre a resposta, você percebe que estava fazendo uma tempestade em copo d'água.


 

Levando pacotes: Mova sempre a carta de valor mais alto possível, junto com as seguintes, para o espaço vizinho à esquerda. Esse algoritmo assegura uma solução, embora não necessariamente a mais simples.

O exemplo mostra o algoritmo em ação. Observe que, uma vez obtida a situação desejada (123456789), o algoritmo se detém automaticamente.

Levando pares: É possível passar de uma disposição a outra somente quando estas diferem por um número par de transposições. Esse número de transposições é obtido contando-se quantos "saltos de ordem" as cartas precisam dar. Se temos, por exemplo, 251364 e queremos levar à ordem 123456, a carta 1 deve dar dois saltos (sobre o 5 e o 2), a carta 3 deve dar um salto (sobre o 5). A carta 6 não requer nenhum salto. Finalmente, a carta 4 deve dar dois saltos (sobre o 6 e o 5). Total: 5 saltos. Sendo uma quantidade ímpar, as duas disposições estão desconectadas, isto é, é impossível levar as cartas para a ordem natural.

Também para ir de 654321 a 123456, o número necessário de saltos seria ímpar, fazendo a tarefa impossível.

A razão da condição necessária que enunciamos é que ao deslocarmos duas cartas vizinhas, sem alterar a sua ordem, produzimos uma quantidade par de transposições: n transposições para uma das cartas do par e mais n para a outra carta.

Levando trios: Os cinco casos propostos (a), (b), (c), (d) e (e) podem ser resolvidos, cada um, com apenas três movimentos, que descreveremos usando as letras U, V, W, X, Y e Z.

(a) V² W (Aplica-se primeiro W, depois V e de novo V.)

(b) Y² Z (c) Y W Y (d) U V ² (e) WY²

Tendo resolvido as cinco transposições de pares de cartas vizinhas, asseguramos que podemos passar de uma disposição qualquer para outra qualquer. Por quê?

NR: Para ser mais instigante, este artigo, propositalmente não esgota o assunto, deixando várias questões a serem colocadas e respondidas. Boa sorte, leitor!