|
Torre de Hanói
As funções exponenciais podem crescer muito rápido.
Existe uma lenda, muitas vezes atribuída a Eduard Lucas, um matemático francês no final de 1800, relativo a um quebra-cabeça que está sendo jogado em um templo de monges perto de Hanói, no Vietnã. O quebra-cabeça é composto por três estacas e 64 discos de ouro. Todos os discos empilhados para começar uma cavilha, a fim do tamanho com o maior na base e menor na parte superior. Os monges devem mover todos os discos do pino de partida para uma outra cavilha, movendo um disco de cada vez, enquanto que nunca colocando um disco maior no topo de um disco menor.A lenda prevê que quando os monges terminarem esta tarefa, o mundo vai acabar.
Na demonstração abaixo, selecione um número de discos usando a caixa suspensa abaixo do jogo. Mova os discos, pressionando o botão para o a fonte seguido do botão para o pino de destino. Por exemplo, para mover o primeiro disco no pino 1 a pino 2, pressione Pino 1 e pressione Pino 2 . Para começar pressione reset .
Para ver o número ideal de movimentos para o número selecionado de discos, verifique Mostrar # movimentos .
|
|
|
|
|
|
|
|
|
|
|
|
* Imagens reais, mas, meramente ilustrativas.
|
O Fim do Mundo?
Mesmo se a lenda fosse verdade, não haveria muito para se preocupar. Considere o seguinte: para mover um disco é trivial. Para mover-se dois discos requer simplesmente movendo um disco e, em seguida, movendo-se o disco da base para o pino desocupado, e movendo-se o primeiro disco no topo. Três discos requerem executar a tarefa anterior (dois discos), em seguida, movendo-se o disco da base e movendo os dois discos de volta ao topo. Deste modo podemos provar que qualquer número de discos podem ser movidos. Existem três passos principais necessários para mover  discos
| 1. |
Mova os principais  discos para outro pino.
|
| 2. |
Mova o último disco para o pino aberto.
|
| 3. |
Mova os primeiros  discos na parte superior do último disco.
|
Então, se nós deixarmos  ser o número de passos para  discos, em seguida, de forma recursiva,  . Desde  (trivialmente), os primeiros termos gerados por esta fórmula são  . Esta é idêntica à sequência gerada pela função não-recursiva  para  . Assim, com três pinos, um número qualquer de discos pode ser movido a partir de uma cavilha de partida para uma outra cavilha. Por que, então, não há nada para se preocupar? Se os monges fizeram um movimento a cada segundo, ele vai levá-los  segundos, ou cerca de 585,000 milhões anos, para terminar a sua tarefa designada.
|
