A tarefa do quebra-cabeça “tag” é organizar os blocos numerados. Hoje, os matemáticos resolveram o problema inverso - como misturar o quebra-cabeça.Você provavelmente jogou tag. Este é um jogo frustrante, mas viciante, composto por 15 peças e um espaço vazio, organizados em uma grade de 4 por 4. A tarefa é mover as peças e organizá-las em ordem crescente de números ou, em algumas versões, montar uma imagem a partir delas.
Após seu surgimento na década de 1870, entrou no conjunto padrão de jogos. Além disso, atraiu a atenção de matemáticos que estudam quebra-cabeças de vários tamanhos e configurações iniciais há mais de um século.
Hoje
há novas evidências de uma solução para o “jogo aos 15” , mas em ordem inversa. Os matemáticos Yoon Chu e
Robert Howe, da Stony Brook University, determinaram o número de movimentos necessários para transformar um campo ordenado em aleatório.
Uma versão do problema "tag" com a randomização foi proposta por
Percy Deaconess em 1988. Ele sugeriu que quebra-cabeças aleatórios de qualquer tamanho exigissem aproximadamente
n 3 movimentos. Ou seja, para um campo de 4 por 4, serão necessários 4 movimentos de
3 ou 64 e para um campo de 10 por 10, 10
3 ou 1.000 movimentos. (Embora ainda sejam chamados de "Quinze", os campos podem ter qualquer número de espaços que compõem o quadrado correto.)
O matemático da Universidade de Stanford, Deaconess, sugeriu que sua versão do problema dos “15 jogos” é representativa de uma grande classe de problemas semelhantes de randomização. Muitas dessas tarefas estão ligadas às características fundamentais da natureza, por exemplo, com a mudança de locais dos pares de bases de DNA que causam uma mutação genética e com a maneira como as moléculas são separadas umas das outras e se tornam desordenadas - isso acontece quando o gelo derrete.
Deaconess esperava que, tendo compreendido o problema do emaranhado de "manchas", poderíamos entender como os sistemas ordenados como um todo se transformam em um estado uniformemente misto.
Em situações como "etiqueta", a aleatoriedade se desenvolve um passo de cada vez. Imagine um campo totalmente ordenado, com uma unidade no canto superior esquerdo e um espaço vazio no canto inferior direito. Movemos os ladrilhos para que o espaço vazio se mova um quadrado em qualquer uma das quatro direções possíveis: para cima, para baixo, esquerda ou direita. (Por uma questão de elegância matemática, Chu e Howe consideraram um campo cujas bordas estão conectadas umas às outras em um anel, para que os ladrilhos nunca fiquem presos nos cantos.) Vamos fazer uma escolha aleatória. Agora o campo está em uma nova configuração - não exatamente em uma ordem, mas não muito longe dela. Repita esse processo. Se você continuar movendo o quadrado vazio, o campo se afastará cada vez mais do local pedido original.
Uma característica importante desse processo é que, em cada etapa, a configuração de campo subsequente depende apenas da configuração atual. Isso lembra um jogo em Monopólio: a probabilidade de jogar dados e mover dois quadrados de Park Place para Boardwalk não depende das jogadas que nos levaram à gaiola de Park Place.
Os quinze arrepios rastejam gradualmente em direção ao distúrbio, um passo de cada vez. Muitos outros sistemas, como o derretimento do gelo, são randomizados da mesma maneira. Os matemáticos estudam esse fenômeno usando modelos chamados "cadeias de Markov". As cadeias de Markov são uma maneira formal de estudar qualquer processo de randomização no qual a configuração subsequente do sistema dependa apenas da configuração atual. Eles estão na vanguarda de uma compreensão matemática do acaso.
"As correntes de Markov estão na média de ouro - por um lado, ainda podemos analisá-las, por outro, elas descrevem muitos dos fenômenos que nos interessam", diz o matemático Yuval Perez, que realizou um trabalho importante na teoria das probabilidades.
Em seu novo trabalho, Chu e Howe trabalharam com a randomização de "tag", assim como com a cadeia de Markov. Em particular, eles consideraram um conjunto de números chamado de "matriz de transição" da cadeia de Markov. A matriz de transição é um extenso conjunto de números que determina a probabilidade de um "jogo aos 15" se mover de uma configuração para outra se decidirmos mover o espaço vazio aleatoriamente.
Compreender a matriz de transição é a chave para calcular o número de movimentos necessários para randomizar ou embaralhar um campo ordenado. Em particular, Chu e Hou se concentraram em definir o conjunto de números que caracterizam a matriz de transição - números chamados "autovalores".
"Ao coletar informações suficientes sobre os autovalores, podemos obter informações de mixagem muito precisas", diz Howe.
A matriz de transição para "spots" contém uma enorme quantidade de informações que refletem trilhões de configurações diferentes que mesmo um pequeno campo de 4 por 4. Pode criar, mais informações do que os matemáticos podem processar diretamente. Portanto, em vez de analisar a matriz de transição em cada etapa do caminho do campo até a randomização, Chu e Howe descobriram como caracterizar o comportamento médio de toda a matriz de transição ao longo da jornada.
A abordagem deles é semelhante à de como você pode descobrir onde é mais provável que acabemos no campo do monopólio após 1000 jogadas de dados: você pode rolá-las tantas vezes ou apenas pegar a média de várias jogadas e extrapolá-las.
Usando essa técnica, Chu e Howe calcularam os autovalores da matriz de transição, que informaram quantos movimentos precisavam ser feitos para randomizar os "pontos". Eles até receberam duas respostas com base em duas definições diferentes de aleatoriedade.
Primeiro, eles consideraram um campo aleatório, no qual cada bloco com igual probabilidade pode estar em qualquer quadrado do campo. Com essa definição, eles descobriram que para a randomização de um campo
n para
n, n 4 movimentos seriam necessários (ou seja, 256 etapas para um campo 4 por 4 e 10.000 etapas para um campo 10 por 10). Isso é mais do que Diaconis previu (como lembramos, ele sugeriu
3 etapas).
A segunda definição de acaso por Chu e Hou foi mais rigorosa. Eles consideraram um campo aleatório, que com igual probabilidade poderia estar em qualquer uma de suas muitas configurações possíveis. Eles provaram que seriam necessários mais alguns passos para alcançar essa definição de aleatoriedade - não mais que
n 4 log
n movimentos.
Chu e Howe demonstraram que a randomização do “jogo dos 15” é mais difícil do que Diaconis previu; de certo modo, isso sugere que leva mais tempo do que o esperado para eliminar completamente a ordem no sistema. Graças ao seu trabalho, a "etiqueta" tornou-se uma das poucas tarefas de randomização em que, de acordo com Howe, "de fato, o número de etapas necessárias para a randomização é conhecido".
Howe e Perez estão agora trabalhando na expansão das evidências. Entre outras coisas, eles estão interessados em saber se o campo atinge um estado aleatório com tamanho crescente por um salto acentuado. Os sistemas com esse comportamento não parecem aleatórios e, após apenas um passo, de repente se tornam assim.
"Não entendemos completamente quais cadeias de Markov demonstram tanta repentina", diz Perez. "Este é um dos maiores mistérios nesta área."