Usando indução, mostre as seguintes afirmações: A Torre de Hanoi é um jogo que consiste em um tabuleito com 3 hastes (A, B e C) e uma coleção de discos de tamanhos (raios) diferentes. Os discos têm orifícios perfurados em seus centros, de modo a poderem encaixar os discos nas hastes do tabuleiro. Inicialmente, todos os discos estão na haste A , dispostos por tamanho (do maior, na base, para o menor, no topo). O objetivo é transferir todos os discos da haste A para haste B com o menor número possível de movimentos. Cada movimento consiste em tirar o disco de cima de uma das hastes e colocá-lo em outra haste, com a condição de não se colocar um disco maior em cima de um disco menor. Mostre que é possível, com movimentos, transferir todos os discos da haste A para haste B.

Passo 1

Vamos falar sobre o problema da Torre de Hanoi. Nesse jogo, temos 3 hastes (A, B e C) e uma quantidade de discos com tamanhos diferentes. Todos os discos começam na haste A, do maior na base para o menor no topo. O objetivo é mover todos os discos da haste A para a haste B, usando o menor número de movimentos possível. Cada movimento envolve pegar o disco de cima de uma haste e colocá-lo em outra, mas sempre colocando um disco menor em cima de um maior. Vamos usar o Princípio da Indução Matemática para mostrar que precisamos de no máximo movimentos para transferir todos os discos da haste A para a haste B.

Passo 2

Primeiro, vamos entender o que é o Princípio da Indução Matemática. Esse princípio nos permite provar que uma afirmação é verdadeira para todos os números naturais. Ele tem dois passos principais:
  1. Caso Base: Verificamos se a afirmação é verdadeira para .
  2. Passo Indutivo: Assumimos que a afirmação é verdadeira para algum e, com base nessa suposição, mostramos que ela também é verdadeira para .
Vamos aplicar isso ao nosso problema.

Passo 3

Caso Base ( ):
Se temos apenas 1 disco, a solução é simples: mover o disco diretamente da haste A para a haste B. Isso requer apenas um movimento.
Vamos verificar se nossa fórmula funciona aqui:
Portanto, para , precisamos de 1 movimento, que coincide com nossa observação. O caso base está verificado.

Passo 4

Passo Indutivo:
Agora, vamos supor que a afirmação é verdadeira para , ou seja, que com discos, podemos transferi-los da haste A para a haste B em movimentos.
Nosso objetivo é mostrar que, para discos, podemos realizar a transferência em movimentos.

Passo 5

Vamos considerar discos. A estratégia para mover esses discos segue dois grandes passos:
  1. Mover os discos menores da haste A para a haste C: De acordo com nossa suposição indutiva, isso leva movimentos.
  2. Mover o maior disco (o de tamanho ) da haste A para a haste B: Isso leva 1 movimento.
  3. Mover os discos da haste C para a haste B: Novamente, usando a suposição indutiva, isso leva mais movimentos.

Passo 6

Vamos somar os movimentos de cada etapa:
Simplificando:
Isso mostra que para discos, precisamos de movimentos, o que confirma nossa afirmação.

Resposta

Portanto, por indução matemática, mostramos que é possível transferir discos da haste A para a haste B em exatamente movimentos.

Exercícios relacionados

Determine f e g , dado que
(b)
Usando indução, mostre as seguintes afirmações: é múltiplo de 9 para .
Usando indução, mostre as seguintes afirmações: para .
Determine uma equação da reta que satisfaça as condições dadas a seguir:
(d) Passa pelo ponto e tem inclinação -1 .