jogos

You are currently browsing articles tagged jogos.

Problema

Um jogo consiste em passar todos os discos, movendo um disco de cada vez, do primeiro pino para o último, usando o pino do meio como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.

Figura 1

Figura 1

Quantos movimentos, no mínimo, são necessários para movimentar os 4 discos da figura acima para o último pino?

Solução



Discussão

Esse jogo é baseado na torre de Brama que, segundo um mito indiano, seria constituída de 64 discos de ouro puro de tamanhos diferentes colocados em uma das 3 agulhas de diamantes fixadas em uma placa. O maior disco seria a base da torre e o menor, seu topo. A tarefa dos monges seria transportar a torre para a outra agulha movendo um disco de cada vez, e nunca colocando um disco maior sobre outro menor. Ainda segundo o mito, quando a tarefa fosse cumprida, o mundo desapareceria.

O quebra cabeça foi inventado pelo matemático francês Édouard Lucas. Ele teve inspiração no mito para construir o jogo das Torres de Hanói em 1883. Já seu nome foi inspirado na torre símbolo da cidade de Hanói, no Vietnã.

Vamos resolver o seguinte problema: queremos saber o número mínimo de movimentos para resolver uma torre de Hanoi com n discos.

1) Para começar, vejamos o que acontece quando o número de discos é pequeno.

• Para n=1, isto é, 1 disco. Bom, 1 movimento foi suficiente!

Figura 2

Figura 2

• Para n=2, isto é, 2 discos. Aqui foram 3 movimentos!

Figura 3

Figura 3

• Para n=3, isto é, 3 discos. Como já sabemos como resolver a torre com 2 discos, vamos passar a “minitorre” para o pino do meio. Assim o maior disco fica “livre” e o passamos para o último pino. E por fim passamos a “minitorre” para o último pino. São 7 movimentos.

Figura 4

Figura 4

• Para n=4, isto é, 4 discos. Usando a mesma estratégia, passamos a “minitorre” para o pino do meio, livramos o maior disco, o passamos para o último pino e por fim passamos a “minitorre” para o último pino. 15 movimentos.

Figura 5

Figura 5

2) Do mesmo modo, para n discos, podemos usar a mesma estratégia. Suponha que sabemos como resolver uma torre de n-1 discos. Passamos a “minitorre” de n-1 discos para o pino do meio, para deixar o maior disco livre e o passamos para o último pino. Por fim passamos a “minitorre” para o último pino.

Figura 6

Figura 6

Vamos dizer que T_n é o número mínimo de movimentos para resolver uma torre de n discos. Observe a figura anterior. Para movimentar a “minitorre” para o pino do meio usamos T_{n-1} movimentos. Depois mais 1 movimento para passar o maior disco para o último pino. Finalmente mais T_{n-1} movimentos para passar a “minitorre” para o último pino. Logo, são T_{n-1} +1+T_{n-1}=2T_{n-1}+1 movimentos. Mas será que essa estratégia usada nos dará o menor número de movimentos? Se o menor número de movimentos é T_n então

(1)   \begin{equation*} T_n \leq 2T_{n-1}+1. \end{equation*}

Por outro lado, para podermos passar o último disco para o último pino, devemos deixá-lo livre. Para isso devemos passar a “minitorre” para o pino do meio. Isso requer, no mínimo T_{n-1} movimentos. Mais 1 para passar o maior disco para o último pino e por fim usamos, no mínimo, mais T_{n-1} movimentos para passar a “minitorre” para o terceiro pino. Assim, teremos, no mínimo, T_{n-1} +1+T_{n-1}=2T_{n-1}+1 movimentos. Logo

(2)   \begin{equation*} T_n \geq 2T_{n-1}+1. \end{equation*}

De (1) e (2) temos que

(3)   \begin{equation*} T_n = 2T_{n-1}+1. \end{equation*}

3) Assim, temos a lei de recorrência para gerar o número mínimo de movimentos para resolver a torre de Hanoi com n discos. Então vamos gerar os primeiros valores. Sabemos que T_1=1. Usando (3) temos

    \begin{align*} T_2 &= 2T_1+1 = 2(1)+1 = 3=2^2-1\\ T_3 &= 2T_2+1 = 2(3)+1 = 7=2^3-1\\ T_4 &= 2T_3+1 = 2(7)+1 = 15=2^4-1\\ T_5 &= 2T_4+1 = 2(15)+1 = 31=2^5-1\\ \vdots &\\ T_n &= 2^n-1. \end{align*}

E, a partir dos resultados dos números mínimos de movimentos, conseguimos induzir uma fórmula fechada

(4)   \begin{equation*} T_n &= 2^n-1. \end{equation*}

4) Provemos pelo princípio da indução finita que (4) vale para qualquer valor de n \in \mathbb{N}^*.

(I) A fórmula vale para n=1 pois, T_1=2^1-1=1.

(II) Admitamos que a fórmula é válida para n, isto é, T_n=2^n-1 é o número mínimo de movimentos. Provemos que a fórmula é verdadeira para n+1, isto é, o numero mínimo de movimentos é T_{n+1}=2^{n+1}-1. Observe a ‘figura 7’.

Figura 7

Figura 7

São 2^n-1 movimentos para passar a “minitorre” para o pino do meio, mais 1 movimento para passar o maior disco para o último pino e mais 2^n-1 movimentos para passar a minitorre para o último pino. Assim temos

    \begin{gather*} T_{n+1} = (2^n-1) + 1 + (2^n-1)\\ T_{n+1} = 2^{n+1}-1. \end{gather*}

Pelo princípio da indução finita, os passos (I) e (II) demonstram a fórmula

    \[ \boxed{T_n=2^n-1}. \]

Um pequeno resultado!

Para a torre de Brama do mito, que tem 64 discos, o número mínimo de movimentos será

    \[ T_{64} = 2^{64}-1= 18446744073709551616. \]

Se movimentarmos um disco por segundo e como cada ano tem aproximadamente 365 \cdot 24 \cdot 60 \cdot 60 segundos, então o tempo mínimo necessário para movimentar os 64 discos para o ultimo pino é aproximadamente 584942417355 anos. Acho que não precisamos nos preocupar com o fim do mundo!

😉

Solução para 5 discos



Tags: , ,