As torres de Hanói (originalmente, a torre de Hanói ) é um jogo de quebra - cabeça imaginado pelo matemático francês Édouard Lucas e consiste em mover discos de diâmetros diferentes de uma torre de "partida" para uma "torre de chegada.» Por meio de um «intermediário» torre, e isso em um mínimo de movimentos, respeitando as seguintes regras:
Supõe-se que esta última regra também seja respeitada na configuração inicial.
O problema matemático das torres de Hanói foi inventado por Édouard Lucas . É publicado no volume 3 de sua Récréations mathiques , publicada postumamente em 1892 . Ele anuncia que esse problema se deve a um de seus amigos, N. Claus de Siam ( anagrama de Lucas d'Amiens, sendo Amiens sua terra natal), supostamente professor do colégio de Li-Sou-Stian (anagrama de Saint Louis , o ensino médio onde Lucas lecionava).
Sob o título " Os Brahmes estão caindo ", Lucas relata que "N. Claus do Sião viu, em suas viagens para a publicação dos escritos do ilustre Fer-Fer-Tam-Tam, no grande templo de Benares , au- abaixo da cúpula que marca o centro do mundo, três agulhas de diamante, plantadas em uma laje de bronze, de um côvado de altura e do tamanho do corpo de uma abelha. Em uma dessas agulhas, Deus enfiou, no início dos séculos, 64 discos de ouro puro, o maior repousando sobre o latão, e os outros, cada vez mais estreitos, sobrepostos ao topo. É a torre sagrada de Brahmâ . Noite e dia, os padres se sucedem nos degraus do altar, ocupados em transportar a torre da primeira agulha para a terceira, sem se desviar das regras fixas que acabamos de indicar e que foram impostas por Brahma. Quando tudo acabar, a torre e os Brahmins cairão, e será o fim dos mundos! " .
Conforme mostrado abaixo, um jogo de 64 discos requer um mínimo de 264 -1 movimentos. Supondo que leve 1 segundo para mover um disco, o que faz 86.400 movimentos por dia, o jogo terminaria após cerca de 213 trilhões de dias, o que é aproximadamente equivalente a 584,5 bilhões de anos, ou 43 vezes a idade estimada do universo (13,7 bilhões anos de acordo com algumas fontes).
É fácil demonstrar por indução que se n for o número de discos, leva pelo menos 2 n - 1 movimentos para atingir seus fins, uma quantidade que aumenta muito rapidamente com n . Na verdade, sejam A, B e C as três localizações das torres; denotam x n o número de deslocamentos de discos necessários para o deslocamento de uma torre completa. Para mover uma torre de n discos de A para C, realizamos estas três etapas:
O número de deslocamentos de discos, portanto, verifica a relação de recorrência:
o que dá bom
Podemos mostrar que o método descrito aqui fornece a sequência ótima (aquela que requer menos movimentos), e que esta é única. Na verdade, para mover a torre de n discos de A para C, devemos necessariamente, em um momento ou outro, mover o maior disco de A para C, e para fazer isso, devemos ter empilhado os n -1 primeiros registros em B .
O problema das torres de Hanói é visto em algoritmos ( programação ), onde oferece um exemplo do poder e legibilidade de programas definidos recursivamente (outro exemplo é a ordenação de árvores ). Na verdade, o método de resolução visto anteriormente leva a um algoritmo recursivo , descrito abaixo. Os parâmetros do procedimento de Hanói são:
Podemos generalizar a resolução recursiva no caso em que os discos são inicialmente arranjados aleatoriamente nas três localizações, em vez de empilhados na primeira (a posição inicial é arbitrária). O objetivo será reagrupar os n discos no local de destino A. Numeramos os n discos de 1 an em ordem de tamanho crescente e denotamos por P k a posição do disco numerado k . Partimos da seguinte observação: inevitavelmente será necessário, em algum momento, mover o maior disco de P n para A. O raciocínio recursivo é então semelhante ao anterior:
Ao contrário do caso particular discutido acima, o local de partida depende do layout dos discos. Devemos também distinguir o caso em que o disco n já está no lugar certo (P n = A). Nesse caso, seguir o método anterior não seria o ideal: a segunda etapa é desnecessária e podemos mesclar a primeira e a terceira etapas agrupando diretamente os primeiros n -1 discos em A.
O algoritmo generalizado, portanto, torna-se:
procédure Hanoï-généralisé(n, A) si n ≠ 0 si Pn = A Hanoï-généralisé(n-1, A) sinon Hanoï-généralisé(n-1, I) Déplacer le disque de Pn vers A Hanoï-généralisé(n-1, A) fin-si fin-si fin-procédureObserve que a última chamada recursiva pode ser substituída por uma chamada para o procedimento de Hanoi do caso particular visto anteriormente, uma vez que todos os n -1 primeiros discos são então empilhados em I.
Com o mesmo raciocínio de antes, mostramos que esse algoritmo fornece a sequência ótima única. Podemos expressar o número de acertos em função do número n de discos, sua disposição e a localização A de chegada: denotamos isso y n (A).
Portanto, temos a seguinte relação de recorrência:
Podemos, então, expressar y n (A) como uma soma de potências de 2, onde um termo é adicionado se e somente se o disco correspondente estiver mal colocado:
onde b k é 0 se o disco k estiver bem colocado, 1 caso contrário.
Na pior das hipóteses, todos os discos são perdidos. Temos então . É interessante notar que a situação inicial usual é um desses piores casos.
Também existe um procedimento iterativo para resolver o problema das torres de Hanói de forma otimizada. Consiste em realizar os dois movimentos seguintes sucessivamente, designando por A, B, C as três voltas (da esquerda para a direita):
e continuar esses dois deslocamentos iterativamente até que a torre completa seja deslocada, o último deslocamento sendo então limitado ao do menor disco no topo da torre. A ação "mover outro disco" é inequívoca, pois, além do menor disco, apenas um movimento de disco é possível.
Ao contrário do procedimento recursivo, o procedimento iterativo não utiliza nenhuma memorização da árvore de deslocamentos a realizar e apenas requer que se lembre se devemos mover o menor disco ou não, e em que direção os deslocamentos do menor disco são feitos. Também permite, a qualquer momento, voltar à situação inicial: basta inverter a direção em que se move o menor disco. No entanto, as razões pelas quais esse algoritmo resolve o problema são menos aparentes do que para o algoritmo recursivo.
Podemos explicar isso observando que, na solução ótima, necessariamente movemos o menor disco exatamente uma vez em dois, porque movê-lo duas vezes consecutivas não seria o ideal, e mover o outro disco duas vezes consecutivas também. Como movemos esse disco menor ainda não foi determinado.
Suponha que a torre de n discos esteja inicialmente na localização A, e que queremos movê-la para a localização C. Mostramos por indução em n que a iteração dos dois movimentos descritos anteriormente produz a sequência ótima, se a direção na qual o disco menor é movido é A → B → C → A (da esquerda para a direita) para n par, ou A → C → B → A (da direita para a esquerda) para n ímpar. De fato :
Suponha que as torres sejam 1, 2 e 3.
Um deslocamento da torre n ° i para a torre n ° j é observado i + j.
Assim, o deslocamento 3 designa o deslocamento da torre 1 em direção à torre 2 e da torre 2 em direção à torre 1, mas não há ambigüidade possível: o disco menor será colocado sobre o maior.
Da mesma forma, o deslocamento 4 designa o deslocamento da torre 1 em direção à torre 3 e da torre 3 em direção à torre 1.
E, finalmente, o deslocamento 5 designa o deslocamento da torre 2 em direção à torre 3 e da torre 3 em direção à torre 2.
Quando o número de discos é par, os movimentos a serem realizados são 3,4,5,3,4,5,3,4,5 ... quantas vezes forem necessárias (a seqüência 3,4,5 é repetida vezes).
Quando o número de discos é ímpar, os deslocamentos a serem realizados são 4,3,5,4,3,5, ... quantas vezes forem necessárias (a sequência 4,3,5 se repete vezes e termina com o deslocamento da torre 1 para a torre 3).
Suponha que os discos sejam coloridos de preto com branco, alternadamente. Por conveniência, também será assumido que as bases das três hastes são coloridas em preto ou branco. A base que sustenta a torre inicial é colorida em cor diferente da do disco maior, de forma a respeitar a alternância das cores. As outras duas bases são uma preta e a outra branca. Os discos são movidos iterativamente de acordo com as duas regras a seguir:
Podemos representar o jogo das Torres de Hanói por um grafo abstrato , cada vértice do grafo representando um possível arranjo dos N discos nas três voltas, uma aresta conectando dois vértices se houver um movimento de um disco que permite passar de um arranjo, representado por um dos vértices, ao outro. A etiquetagem dos vértices é baseada na posição dos discos no arranjo que eles representam: lemos da esquerda para a direita a qual torre cada disco pertence, começando pela posição do maior disco.
O diagrama mostra a árvore do jogo com três discos. A posição inicial está localizada em um vértice do triângulo, por exemplo AAA, a posição final sendo outro vértice, BBB ou CCC. A cor das bordas indica que o disco se move: vermelho para o disco menor, amarelo para o disco intermediário e azul para o disco grande.
Mostramos que, para todo N, o gráfico das Torres de Hanói com N discos é idêntico ao obtido de um Triângulo de Pascal de ordem 2 N , onde conectamos os coeficientes binomiais ímpares por uma aresta.
A tarefa Torre de Hanoi é usada na pesquisa em psicologia , principalmente na resolução de problemas . Também é usado como teste neuropsicológico .
Esta tarefa é sensível a disfunções frontais e pré - frontais .
Este teste permite, assim, a avaliação das funções executivas , como planejamento , memória de trabalho e inibição .
O desempenho na Torre de Hanói depende das capacidades de inibição , da memória de trabalho , da memória de procedimento e do fluido de inteligência .
No entanto, a inibição requer a supressão da atividade do córtex motor primário , do córtex frontal inferior direito e da área motora adicionalmente. A memória de trabalho significa a porção dorso-lateral do córtex frontal que permite a manipulação ativa e controle de informações. Da mesma forma, o planejamento se correlaciona com a ativação da parte dorsal do córtex pré-frontal , do córtex parietal e pré-motor e do cerebelo.
Entendemos por que a Torre de Hanói é sensível a disfunções frontais e pré-frontais.
Este teste está próximo do teste da Torre de Londres e também do teste das Torres de Toronto.