Número de Deus

Pegue um Cubo Mágico e embaralhe do jeito que quiser: dez, cem, mil giros. Não importa como ele fique, existe uma sequência de no máximo 20 movimentos que o deixa resolvido de novo. Esse número tem nome: Número de Deus.

Número de Deus = 20

Qualquer posição do Cubo Mágico pode ser resolvida em 20 movimentos ou menos. E existem posições que precisam de exatamente 20.

Por que “de Deus”?

Imagine alguém que sabe tudo. Olhando para qualquer cubo embaralhado, essa pessoa enxergaria na hora o caminho mais curto até a solução. Essa estratégia perfeita ganhou o apelido de algoritmo de Deus, e o Número de Deus é o tamanho desse caminho no pior caso: a maior quantidade de movimentos que alguém perfeito precisaria usar, considerando todas as embaralhadas possíveis.

Para nós, simples mortais, a história é outra. Descobrir esse número levou cerca de 30 anos e exigiu muito poder de computação.

43 quintilhões de possibilidades

O desafio está no tamanho do cubo. Com 1 movimento, ele pode chegar a 18 posições diferentes. Com 2, surgem 243 posições novas; com 3, mais 3.240. A cada giro a mais, as possibilidades se multiplicam por cerca de 13, e no fim o Cubo Mágico tem:

43.252.003.274.489.856.000 posições

Mais de 43 quintilhões de jeitos diferentes de estar embaralhado.

Para ter uma ideia, se você conseguisse olhar uma posição por segundo, sem parar, levaria cerca de 1,4 trilhão de anos para ver todas: quase 100 vezes a idade do universo. E se existisse um cubo de 5,7 cm para cada posição, empilhando todos você teria uma torre de uns 260 anos-luz.

De onde vem esse número? As 8 quinas podem ser arrumadas de 8! = 40.320 jeitos, e 7 delas podem girar em 3 posições (3⁷); a última quina é obrigada a acompanhar as outras. As 12 arestas podem ser arrumadas de 12! = 479.001.600 jeitos, e 11 delas podem ser viradas (2¹¹). Por fim, divide-se tudo por 2, porque não dá para trocar só duas peças de lugar sem mexer em nenhuma outra. É por isso que um cubo montado com uma peça virada nunca se resolve (veja os casos impossíveis).

A conta

8! × 3⁷ × 12! × 2¹¹ ÷ 2 = 43.252.003.274.489.856.000

O que conta como um movimento?

Também é preciso combinar o que é “um movimento”. No Número de Deus, cada giro de uma face conta como um, seja de 90° (como R ou U') ou de 180° (como R2). É a chamada métrica de meia volta (HTM, na sigla em inglês). Se essas letras ainda são novidade para você, veja os movimentos básicos.

Se cada giro de 180° contar como dois, a métrica muda (métrica de quarto de volta, ou QTM) e o Número de Deus passa a ser 26, como provaram Tomas Rokicki e Morley Davidson em 2014.

Uma caçada de 30 anos

Desde o começo dos anos 80, pesquisadores atacaram o problema por dois lados. De um, tentavam mostrar que algumas posições exigem muitos movimentos: o limite mínimo. Do outro, que todas podem ser resolvidas com no máximo um certo número: o limite máximo. Quando os dois se encontrassem, o Número de Deus estaria descoberto.

O primeiro limite mínimo veio de uma conta: com 17 movimentos ou menos dá para chegar a cerca de 20 quintilhões de posições, menos da metade do total. Então algumas posições precisam de pelo menos 18.

O limite máximo começou bem mais alto. Em 1981, o matemático Morwen Thistlethwaite mostrou que 52 movimentos sempre bastam. Depois disso, o número foi caindo: 42 em 1990, 39 e 37 em 1992, 29 em 1995.

Em 1995 veio também a virada do outro lado: Michael Reid provou que o superflip, a posição com todas as peças no lugar e as 12 arestas viradas, precisa de exatamente 20 movimentos. A resposta estava, então, entre 20 e 29.

Faça o superflip no seu cubo

Com o cubo resolvido, faça esta sequência de 20 movimentos:

U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2

Para voltar ao cubo resolvido, é só repetir a mesma sequência.

2010: a prova final

Com computadores cada vez mais rápidos, o limite máximo caiu para 28 em 2005, 27 em 2006, 26 em 2007 e 25, 23 e 22 em 2008. A palavra final veio em julho de 2010, com quatro pesquisadores: o programador Tomas Rokicki, o professor de matemática Herbert Kociemba (criador do algoritmo de duas fases, usado até hoje para resolver o cubo por computador), o matemático Morley Davidson e o engenheiro do Google John Dethridge.

Eles não testaram as posições uma a uma, o que seria impossível. Dividiram todas em cerca de 2,2 bilhões de grupos, com 19,5 bilhões de posições cada, e usaram as simetrias do cubo (girar ou espelhar uma posição não muda quantos movimentos ela precisa) e outros atalhos matemáticos para reduzir o trabalho a 55,9 milhões de grupos. Cada grupo levava uns 20 segundos num computador comum. Somando tudo, foram cerca de 35 anos de processamento, feitos em poucas semanas nos computadores do Google.

Resultado

Nenhuma posição precisa de mais de 20 movimentos. Como o superflip precisa de exatamente 20, o Número de Deus é 20.

Quase nenhum cubo precisa de 20

O mais curioso é que as posições que exigem 20 movimentos são raríssimas. Estima-se que existam cerca de 490 milhões delas. Parece muito, mas é mais ou menos 1 em cada 90 bilhões. Duas em cada três posições se resolvem com exatamente 18 movimentos, e 95% com 17 ou 18.

E na prática?

Os speedcubers não procuram o caminho mais curto. Com o método Fridrich (CFOP), um campeão usa perto de 60 movimentos por resolução: o australiano Feliks Zemdegs, ex-recordista mundial, conta que, numa análise das resoluções dele, a média foi de 58. Contra o relógio, reconhecer o caso e girar sem parar vale mais do que economizar giros. Quem está começando pelo método básico usa bem mais movimentos do que isso, e está tudo certo: o importante é resolver.

Mas existe uma categoria oficial que é quase uma disputa para chegar perto de Deus: a Menos Movimentos (Fewest Moves), da WCA. O competidor recebe um embaralhamento, papel, caneta e uma hora para encontrar a solução mais curta que conseguir. O recorde mundial é de 16 movimentos.

Já os computadores acham soluções curtas quase na hora. Programas baseados no algoritmo de duas fases de Kociemba encontram, em frações de segundo, soluções com cerca de 20 movimentos para qualquer embaralhada. É o tipo de programa que costuma estar por trás dos robôs que resolvem o cubo.

E os outros cubos?

No cubo 2x2, o Número de Deus é 11 (ou 14, contando giros de 180° como dois), entre 3.674.160 posições. Como são poucas, dá para testar todas por computador. Para o 4x4 e os cubos maiores, ninguém sabe a resposta: as possibilidades são tantas que nem os supercomputadores dão conta.

Da próxima vez que alguém embaralhar o seu cubo “do jeito mais difícil possível”, você já sabe: existe uma saída com, no máximo, 20 movimentos. Encontrá-la é que são elas.

Fontes: cube20.org (Rokicki, Kociemba, Davidson e Dethridge), cube20.org/qtm e World Cube Association.