Olá João Paulo! Bom dia!
Existe sim uma teoria bastante grande e abrangente
sobre teoria dos grupos aplicada ao cubo de Rubik (popular
"cubo mágico").
Os movimentos que você executa para resolver o cubo na
realidade são comutadores. Para quem não sabe o comutador
de a e b é
[a,b] = a * b * a^(-1) * b^(-1)
Essas notas de conferência explicam detalhadamente sobre a teoria
matemática envolvida:
http://match.stanford.edu/bump/rubik.html
Veja o pdf na página e dá uma olhada nele:
http://match.stanford.edu/bump/rubik.pdf
Achei também essa página que fala mais sobre comutadores:
http://web.usna.navy.mil/~wdj/book/node179.html
Como você vai estudar nas notas de conferência, existe
um movimento interessante que é executado no cubo que permuta
três peças (não existe um movimento no cubo de Rubik que permute somente
duas peças).
A maioria das pessoas acha intuitivo resolver primeiro uma face,
depois
resolver os cantos dessa face, depois resolver as laterais e finalmente
resolver
a face de cima. Claro que essa ordem não precisa ser respeitada e com
o auxilio de um computador, você poderia facilmente escrever um programa
em PROLOG para fazer uma resolução de caminho mais curto (usando
técnicas
de inteligência artificial) para resolver de uma forma mais rápida,
porém menos
intuitiva.
Esse tipo de técnica que eu acabei de mencionar (usando PROLOG) não
é o mesmo que resolver uma equação algébrica ou algo do tipo. É
simplesmente
baseada em busca. Aliás isso já foi feito, de modo que se você for
maníaco por
computação vai ficar fascinado por essa página:
http://people.sunyit.edu/~millerd1/RUBIK.HTM
Eu achei fantástico. Aliás eu acredito que coisas semelhantes a essa
poderiam
ser aplicadas a problemas NP-completos, do tipo achar uma função
potencial
que forneça o único estado nativo de uma molécula de proteína.
Note que o cubo mágico tem "zilhões" de estados, mas apenas um
deles é o
estado resolvido ou correto. Agora imagine que você quer uma função
que
dê a "energia do cubo" em função da posição das peças. E que a cada
movimento você compute, digamos o (delta E) = variação da energia.
Você consegue uma boa função potencial que faça isso e que encontre
o estado resolvido do cubo em um menor número possível de movimentos,
ou no menor tempo?
Esse tipo de analogia física em problemas de matemática é muito
usada.
Eu lembro que li algo sobre o problema dos sapos no site do grupo
teorema.
O problema é assim:
Em cada um dos dez degraus de uma escada existe uma ra. Cada ra pode,
dando um pulo, ir para outro degrau. Por´em, quando uma ra faz isso, ao
mesmo tempo, uma outra ra deve pular a mesma quantidade de degraus em
sentido contr´ario: uma sobe e outra desce. Conseguirao as ras
colocar-se todas juntas no mesmo degrau? Justifique
A idéia é construir um invariante de analogia física para provar que o
problema
proposto não tem solução. Dê uma olhada na solução (ou tente resolver
você mesmo antes de olhar):
http://conesul2006.tripod.com/Material/invariantes2.pdf
Agora voltando ao problema do cubo, devem existir invariantes também
no
cubo que dizem que determinados estados não admitem soluções. Que
invariantes são esses? Fica aqui a indagação :)
[]s
Ronaldo Luiz Alonso
joao paulo de souza mourao wrote:
> alguem sabe como resolver o cubo de rubik(cubo magico) usando teoria
> dos grafos ou teoria dos grupos?
>
> --------------------------------
> ---------------------------------------------------------------------
> Acelerador POP
> Acelere a sua conexão discada em até 19 x. Use o Acelerador POP. É
> grátis, pegue já o seu.
> http://www.pop.com.br/acelerador
> ========================================================================Instruções
> para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> ========================================================================
