O Cubo Mágico e o Número de Deus
O cubo de Rubik, também chamado de cubo mágico, foi criado em 1974 pelo professor húngaro Ernő Rubik. O propósito inicial do cubo era ajudar os alunos de arquitetura a entender problemas tridimensionais, mas logo o quebra-cabeça se tornou uma verdadeira febre, conquistando as lojas de brinquedo dos anos 1980 [1]. Além de ser um dos brinquedos mais vendidos da história, com mais de 400 milhões de unidades comercializadas [2], o cubo de Rubik possui diversas características que ocuparam e seguem ocupando a mente dos matemáticos. A primeira é o número de embaralhamentos possíveis, que é de 43 quintilhões [3]. A título de comparação, se houvesse um cubo com cada embaralhamento possível na Terra, nosso planeta estaria encoberto por um mar de cubos mágicos com 15 km de profundidade [4]. Diante dessa quantidade exorbitante de combinações possíveis, podemos nos perguntar: qual é o número máximo de movimentos necessários para resolver um cubo mágico? Esse problema surgiu em 1981, logo após a viralização do brinquedo, e o número procurado foi chamado de “God’s Number”, ou, em tradução livre, “Número de Deus”. Em outros termos, se tivéssemos um algoritmo que resolvesse o cubo de Rubik sempre com o menor número possível de movimentos, no pior caso, esse algoritmo precisaria de um número de movimentos igual ao Número de Deus. Logo ficou evidente a dificuldade do problema, vinculada à complexidade própria do quebra-cabeça. Uma das primeiras estimativas foi feita pelo matemático britânico Morwen Thistlethwaite, que provou que o Número de Deus é menor ou igual a 52. Após uma pausa nos avanços do problema durante o restante da década de 1980, diversos outros limites superiores para o número procurado foram determinados ao longo dos anos 1990 e 2000. Em 1995, Michael Reid determinou um limite inferior, ao encontrar uma posição chamada de superflip, que exige 20 movimentos para ser resolvida [5]. O problema foi finalmente solucionado em 2010, quando um grupo de pesquisadores de diferentes universidades provou que o Número de Deus é exatamente 20: qualquer que seja a configuração inicial de um cubo de Rubik, ele pode ser resolvido com 20 movimentos ou menos. O grupo de pesquisadores que solucionou o problema foi liderado por Tomas Rokicki, um programador estadunidense, e incluía mais dois matemáticos e um engenheiro. A solução foi baseada em um algoritmo desenvolvido para resolver cada posição em 20 movimentos ou menos. Como já existia o limite inferior de 20, se esse algoritmo fosse capaz de resolver todas as posições possíveis, estaria provado que 20 era o número máximo de movimentos necessários. Para otimização, os pesquisadores levaram em conta que muitas configurações são análogas, utilizando da simetria do problema [5]. O algoritmo foi então aplicado para cada configuração singular, utilizando um número grande de computadores cedidos pela Google©. De acordo com os pesquisadores, se fosse utilizado apenas um computador comum, seriam necessários 35 anos para resolver o problema [5]. É evidente que as soluções mais eficientes para cada problema são difíceis de serem encontradas sem a utilização de computadores, por isso os métodos de resolução utilizados por humanos requerem cerca de 40 movimentos. Ainda assim, é notável o aspecto aparentemente contraditório da situação, em que um quebra-cabeça com uma quantidade extraordinária de configurações iniciais pode ser resolvido com um número de movimentos tão pequeno. Autor: Angelo Zanona Neto. Referências: [1] História do Cubo Mágico. Blog Oncube. Disponível em: <https://www.blog.oncube.com.br/extra/historia-do-cubo-magico/>. Acesso em 07 jun 2024. [2] Matemáticos acham ‘número de Deus’ para resolver o cubo mágico. BBC News Brasil. Disponível em: <https://www.bbc.com/portuguese/ciencia/2010/08/100812_cubomagico_pu#:~:text=Tamb%C3%A9m%20conhecido%20como%20cubo%20de,mais%20vendidos%20em%20escala%20global.>. Acesso em: 12 jun 2024. [3] KORF. R. E. Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. American Association for Artificial Intelligence. 1997. Disponível em: <https://cdn.aaai.org/AAAI/1997/AAAI97-109.pdf>. Acesso em 07 jun 2024. [4] The Rubik Zone. Disponível em: <https://www.therubikzone.com/>. Acesso em 07 jun 2024. [5] God’s Number is 20. Disponível em: <https://www.cube20.org/>. Acesso em 07 jun 2024. [6] ROKICKI, T. Towards God’s Number for Rubik’s Cube in the Quarter-Turn Metric. The Mathematical Association of America. Disponível em: <https://www.tandfonline.com/doi/abs/10.4169/college.math.j.45.4.242>. Acesso em 07 jun 2024. [7] Ernő Rubik. Blog Cubo Velocidade. Disponível em: <https://cubovelocidade.com.br/curiosidade/historia-do-cubo-magico-erno-rubik/>. Acesso em 07 jun 2024.
