Torre de Hanoi

Descrição

A torre de Hanoi (também chamada de torre de Brahma ou torre de Lucas) é um quebra-cabeça que consiste de três bastões e certo número de discos de diferentes tamanhos, que encaixam nos bastões, conforme a figura abaixo:

O problema começa com os discos alinhados do maior para o menor, de baixo pra cima, formando uma figura cônica. O objetivo é levar a pilha de discos para um dos outros bastões, preservando a figura cônica, e obedecendo às regras:

1. Somente um disco pode ser movido de cada vez;

2. Cada movimento consiste em remover um disco do topo de uma pilha e colocá-lo no topo de outra pilha ou em um bastão vazio;

3. Não se pode empilhar um disco sobre um disco menor.

Contexto Histórico

Esse quebra-cabeça foi inventado pelo matemático francês Édouard Lucas em 1883. Existe uma lenda de um templo hindu onde há três grandes pilastras cercadas de 64 discos de ouro. Diz a lenda que os monges têm movido os discos conforme as regras do quebra-cabeça desde tempos imemoriais, e que completo o último movimento, o mundo acabará. Uma versão dessa lenda situa o templo em Hanoi, no Vietnã, daí o nome dado ao quebra-cabeça.

Exemplo com 3 discos

Questões

1. Como resolver o quebra-cabeça no caso geral, isto é, com n discos, em que n é um número natural?

2. Qual o número mínimo de passos na questão 1?

3. Quanto tempo levarão os monges para provocar o final do mundo, caso eles levem 1 segundo em cada passo?

Respostas completas às questões acima.

Tente resolver a Torre de Hanoi simulada abaixo…

Veja um vídeo com a solução da Torre de Hanoi de 4 discos…

Como fazer em casa / na escola

Sugestão 1: Instalação do jogo nos celulares: disponível aqui

Sugestão 2: ROTEIRO DE ESTUDOS DESENVOLVIDO POR protagonismodigital.sed.ms.gov.br:
https://www.protagonismodigital.sed.ms.gov.br/roteiro-de-estudo/construindo-uma-torre-de-hanoi-56377

Sugestão 3: Imprima o arquivo em anexo, cole em um papelão ou material mais rígido. Recorte os círculos, fazendo um furo no meio. Faça uma base de papelão e cole lápis colorido ou palito de churrasco na base.

Arquivo compartilhado para edição: https://www.overleaf.com/9277129981skbygnbqphxt
Arquivo compartilhado para visualização: https://www.overleaf.com/read/rpsvjzyyqjkf