[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 r˜a. Cada r˜a pode,
dando um pulo, ir para outro degrau. Por´em, quando uma r˜a faz isso,
ao mesmo tempo, uma outra r˜a deve pular a mesma quantidade de degraus
em sentido contr´ario: uma sobe e outra desce. Conseguir˜ao as r˜as
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 ========================================================================