segunda-feira, 25 de julho de 2011

Matemáticos começam a desvendar o cubo mágico

O pesquisador Erik Demaine e sua coleção de cubos mágicos com cinco, seis e até sete quadrados por fileira. Ele também possui um dos cubos originais, assinado pelo seu inventor, o húngaro Ernő Rubik

São Paulo – Depois de anos estudando o cubo mágico, o quebra-cabeça tridimensional inventando em 1974 pelo húngaro Ernő Rubik, os cientistas começam a descrever matematicamente seu funcionamento. Matemáticos já conseguem estabelecer a relação entre o número de quadrados e a quantidade máxima de movimentos necessários para resolver o quebra-cabeça (ou seja, para colocar, em cada face, apenas quadrados de uma determinada cor), mas a parte final da equação continua sendo uma mistério.
O feito do grupo liderado por Erik Demaine, do Instituto de Tecnologia de Massachusetts (MIT), e colegas das Universidades de Waterloo e de Tufts, foi criar um algoritmo que funciona para os chamados piores cenários do problema em qualquer tamanho de cubo. O trabalho, que será apresentado no 19º Simpósio Europeu de Algoritmos, em setembro, estabelece que o número máximo de movimentos necessários para resolver um cubo-mágico com N quadrados por fileira é proporcional a N²/logN.
“Proporcional significa que o resultado dessa fórmula ainda precisa ser multiplicado por um fator”, explicou Demaine a INFO Online. “Nós não conseguimos descobrir ainda qual é – e acredito que essa conta não será fácil de vencer, embora as pessoas possam usar nossa abordagem para tentar ir além”.
A mágica quase cai
No ano passado, uma equipe de pesquisadores usou um supercomputador do Google para atingir um feito importante: provar que qualquer embaralhamento de um cubo-mágico poderia ser resolvido com, no máximo, 20 movimentos. O problema é que a equipe considerou apenas o cubo clássico – ou cubo de Rubik  com 3 quadrados por fileira. Infelizmente, para cubos maiores do que o padrão (com quatro ou cinco quadrados por fila), os resultados não são válidos.

Um quadrado por vez?

Para resolver esse problema, a equipe do MIT sabia que a maneira mais direta seria encontrar o pior cenário de um cubo-mágico, ou seja, aquele que exigiria o maior número de movimentos para ser resolvido. Na verdade, a abordagem mais tradicional para resolver um cubo-mágico provou ser justamente a forma mais complicada: focar seu movimento em um quadrado por vez, tentando colocá-lo no lugar movendo o menor número possível de partes.
Essa abordagem resultaria em uma solução de N² – onde N é o número de quadrados por fila. No entanto, não são poucas as vezes em que, mesmo querendo mover apenas um quadrado, se acaba colocando outro também no lugar – e isso reduz o número de possibilidades. Daí, mais alguns cálculos os levaram à conclusão de que o número de movimentos mínimos seria descoberto dividindo essas possibilidades pelo logaritmo de N e multiplicando-a por um fator.
“Só sabemos que esse fator é um número maior do que 1”, diz Demaine. Embora possa parecer inútil apresentar uma equação com um coeficiente faltando, a pesquisa do grupo do MIT tem grande importância. Não só é um primeiro passo, como dá uma dimensão de qual será a solução. “Também vale dizer que a ordem de grandeza de movimentos de um cubo-mágico com 4 quadrados por fileira é tão grande que talvez nunca saibamos a resposta”, diz.
As descobertas podem aplicadas a outros problema de configuração que envolvem, por exemplo, a maneira de empilhar caixas em um depósito – ou até mesmo a programação de um sistema que precise reconfigurar rapidamente seus componentes. “Na verdade, o que a gente queria era mostrar ao mundo como a matemática pode ser divertida”, diz Demaine.

Fonte: http://exame.abril.com.br/tecnologia/ciencia/noticias/matematicos-comecam-a-desvendar-o-cubo-magico?page=2&slug_name=matematicos-comecam-a-desvendar-o-cubo-magico
 

Nenhum comentário:

Postar um comentário