Número de movimentos para o Cubo de Rubik

Em 2010, um problema que estava em aberto por muito tempo foi resolvido. Trata-se de um dos mais populares quebra-cabeças do mundo.

Um time de pesquisadores, incluindo Dr. Morley Davidson, professor de Matemática na Universidade de Kent, apresentou uma pesquisa que mostra que, para qualquer posição inicial do Cubo de Rubik, ele pode ser resolvido com 20 movimentos ou menos.

Utilizando os computadores da Google, a equipe resolveu cada uma das posições iniciais do cubo - 43.252.003.274.489.856.000 ao total - e mostrou que nenhuma delas precisa de mais de 20 passos para ser resolvida.

Existem muitos algoritmos para se resolver o cubo. Eles variam em complexibilidade e número de movimentos requeridos. Os algoritmos que podem ser memorizados por um ser humano, em geral exigem mais de 40 movimentos.

Alguém pode supor que um ser onisciente usaria um algoritmo muito mais eficiente, sempre encontrando a menor sequência de movimentos. Isso é conhecido como o Algoritmo de Deus. O número de movimentos que esse algoritmo usaria no pior dos casos é chamado de Número de Deus. Por enquanto, só se sabe que o Número de Deus é menor ou igual a 20.

De acordo com o time de pesquisadores, levou 15 anos desde a invenção do Cubo de Rubik até que alguém encontrasse a primeira posição que precisava de somente 20 movimentos para ser resolvida. Apropriadamente 15 anos depois disso, foi provado que 20 movimentos eram suficientes para todas as posições.

O Cubo foi criado em 1974 por Erno Rubik, um professor de uma universidade húngara, e foi lançado em 1980, tornando-se um fenômeno global. Em 30 anos de história, mais de 350 milhões de cubos foram vendidos ao redor do mundo.


Retirado daqui, traduzido e adaptado por Raphael Rocha.

Veja também: