I  A resposta de ontem

Os 35 anos de processador do Google

Em julho de 2010, quatro pesquisadores anunciaram no site cube20.org que o Número de Deus do cubo de Rubik é 20. O grupo reunia Tomas Rokicki, programador da Califórnia; Herbert Kociemba, professor de matemática e física em Darmstadt, na Alemanha; Morley Davidson, matemático da Kent State University, em Ohio; e John Dethridge, engenheiro do Google.

O cubo que eles resolveram nasceu nas mãos de Ernő Rubik, professor de arquitetura em Budapeste, montou em 1974 para ensinar movimento no espaço aos alunos. Ele levou semanas para desfazer o próprio embaralhamento.

A conta só ficou possível por um corte inteligente. Kociemba tinha escrito, nos anos 1990, um algoritmo de duas fases (o programa leva o cubo primeiro a um subgrupo de posições fáceis e depois o resolve dali). O programa dele, o Cube Explorer, ainda é distribuído de graça e acha soluções curtas em segundos. O time usou essa ideia ao contrário: dividiu as 43 quintilhões de posições em 2.217.093.120 conjuntos, cada um com 19.508.428.800 posições.

Cada conjunto podia ser resolvido de uma vez, com um programa que preenchia o bloco inteiro em poucos segundos sem buscar o caminho exato de cada posição: bastava provar que nenhuma passava de 20. Quando um bloco resistia, o programa voltava a ele com uma busca mais fina, até cobrir as posições teimosas.

A simetria cortou o trabalho outra vez. O cubo tem 48 simetrias (rotações e reflexos que transformam uma posição noutra equivalente). Usando-as, o grupo reduziu os conjuntos a 55.882.296 casos para rodar.

Quanto custou a conta

Rodar os 55.882.296 casos num computador doméstico levaria décadas. Dethridge conseguiu tempo ocioso nos servidores do Google, e o grupo informou ter consumido o equivalente a 35 anos de processador, espalhados por máquinas da empresa durante algumas semanas.

O Google nunca divulgou quantos servidores usou nem o custo da doação. O grupo também não publicou esse número, e a única medida pública segue sendo os 35 anos de processador anunciados em 2010.

“Toda posição do cubo de Rubik pode ser resolvida em 20 movimentos ou menos.” Tomas Rokicki, Herbert Kociemba, Morley Davidson e John Dethridge, cube20.org, 2010.

O artigo completo saiu em 2013 na revista SIAM Journal on Discrete Mathematics, com o título The Diameter of the Rubik's Cube Group Is Twenty (O diâmetro do grupo do cubo de Rubik é vinte). Diâmetro, aqui, é a maior distância possível entre uma posição e a solução.

II  O Enigma do dia

Quantas jogadas cabem em 16 giros

Dá pra resolver com papel, lápis e uma calculadora de celular. Nenhum cubo precisa estar na mão.

A primeira pista vale para o primeiro giro. O cubo tem 6 faces, e cada face gira de 3 jeitos: um quarto de volta para a direita, um quarto para a esquerda e meia volta.

A segunda pista vale para os 15. Girar a mesma face duas vezes seguidas desperdiça um movimento, porque os dois giros se juntam num só. Tire as 3 jogadas da face que acabou de girar.

A terceira pista vale para a soma. Com n giros existem, no máximo, 18 × 15 × 15 × ... sequências, com o 15 repetido n menos 1 vezes. Some de 1 a 16 giros e compare com 43 quintilhões. A conta de 15 elevado a 15 cabe em qualquer calculadora científica.

A quarta pista: se o total de sequências for menor que o número de posições, alguma posição fica sem caminho de 16 giros. Cada sequência leva a uma posição só.

Onde a conta tropeça

A primeira armadilha é contar 12 jogadas, só os quartos de volta. Na medida usada em 2010, meia volta vale 1 movimento, e o cardápio sobe para 18.

A segunda é achar que sequências demais garantem todas as posições. Muitas sequências diferentes caem na mesma posição, então a conta só prova o limite de baixo.

A terceira é esquecer a soma. A pergunta pede todas as sequências de 1 até 16 giros, e não só as de 16 exatos.

Responda por escrito: o total do primeiro giro, o motivo dos 15 e a soma até 16 giros.

III  Sequência

A conta que para no 17

O primeiro giro tem 18 jogadas, porque 6 faces × 3 giros dá 18. Os 15 vêm de tirar a face que acabou de girar. E a soma de até 16 giros dá perto de 8,4 quintilhões, menos de um quinto das posições. A conta fecha em quatro passos.

1. Um giro: 6 faces × 3 jeitos = 18 sequências.

2. Dois giros em diante: das 18 jogadas, 3 repetem a face anterior e somam com ela, então ficam 15 úteis.

3. Exatamente 16 giros: 18 × 15 elevado a 15 dá perto de 7,9 quintilhões de sequências.

4. De 1 a 16 giros: a soma chega a perto de 8,4 quintilhões, contra 43 quintilhões de posições. Faltam caminhos para pelo menos 34 quintilhões de posições, e todas elas pedem 17 giros ou mais.

O mesmo raciocínio, mais apertado, sobe o piso para 18. Faces opostas giram sem se atrapalhar, e girar a de cima e depois a de baixo leva à mesma posição que a ordem inversa. Descontando essas duplas, as sequências curtas encolhem e não cobrem as posições nem com 17 giros. Logo, existe posição que pede 18 ou mais, e a prova continua sendo de lápis.

Contagem não chega ao 20. O salto final veio de uma posição só, o superflip (as 12 arestas no lugar certo, cada uma com as cores invertidas). Em 1995, o matemático americano Michael Reid mostrou, com busca por computador, que o superflip não sai com menos de 20 giros.

O teto caiu aos poucos. Morwen Thistlethwaite, matemático da Universidade do Tennessee, provou em 1981 que 52 giros bastavam. Rokicki baixou o teto para 22 em 2008. Em 2010, o teto encontrou o piso de Reid, e o intervalo fechou em 20 exato.

A medida importa. Contando só quartos de volta, com meia volta valendo 2, o número sobe: em 2014, Rokicki e Davidson provaram que o limite nessa medida é 26.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes de conferir a solução, e o placar zera quando você espia fora da hora.

“Quantos giros você precisa hoje para resolver um cubo embaralhado?”

Teste hoje: pegue um cubo mágico, aplique 20 giros sorteados (anote cada face e cada direção) e cronometre quanto leva para resolver pelo seu método, contando os giros. Compare o seu total com 20: quem usa o método de iniciante costuma passar de 100.

missão de hoje

No anúncio de 2010, quantos anos de processador o grupo informou ter usado dos servidores do Google pra provar o limite de 20 giros?

Veja o ranking de quem mais acerta →

Como foi a edição de hoje?

Qual edição você quer ver amanhã?

Voto aberto até 08/10, 15h30

Ciência Bizarra

Todo dia, 20:20. Um fenômeno verificado que desafia o senso comum, com a fonte na mesa. Espanto com paper, não com clique.

Quero receber →