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:
- Caso Base: Verificamos se a afirmação é verdadeira para
. - 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:
- Mover os
discos menores da haste A para a haste C: De acordo com nossa suposição indutiva, isso leva movimentos. - Mover o maior disco (o de tamanho
) da haste A para a haste B: Isso leva 1 movimento. - 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)
(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 .
(d) Passa pelo ponto