Questão 171 do ENEM 2011 — 2ª aplicação · Dia 2 · Caderno cinza

Matemática · Recorrências com multiplicação e parcela constante
Nesta questão

Enunciado

A torre de Hanói é um jogo que tem o objetivo de mover todos os discos de uma haste para outra, utilizando o menor número possível de movimento, respeitando-se as regras.

Elemento visual extraído da página 29 do PDF original

As regras são: 1- um disco maior não pode ser colocado sobre um disco menor; 2- pode-se mover um único disco por vez; 3- um disco deve estar sempre em uma das três hastes ou em movimento.

Disponível em: http://www.realidadevirtual.com.br. Acesso em: 28 abr. 2010 (adaptado).

Disponível em: http://www.imeusp.br. Acesso em: 28 abr. 2010 (adaptado).

Usando a torre de Hanói e baseando-se nas regras do jogo, podemos montar uma tabela entre o número de peças (X) e o número mínimo de movimentos (Y):

Número de peças Número mínimo de movimentos
1 1
2 3
3 7
4 15

A relação entre (X) e (Y) é

A)

Y = {2}^{X} – 1

B)

Y = {2}^{X – 1}

C)

Y = {2}^{X}

D)

Y = 2X – 1

E)

Y = 2X – 4

Fonte: INEP · ENEM 2011 · 2ª aplicação · Dia 2 · Caderno cinza.

Dia 2 · Caderno cinza · 2ª aplicação

Resolução comentada

Gabarito: alternativa A.

Para deslocar uma torre com X discos, primeiro precisamos mover os X − 1 discos menores para uma haste auxiliar. Depois movemos o maior disco e, por fim, movemos os menores novamente para cima dele.

Assim, o número mínimo de movimentos dobra o necessário para a torre anterior e acrescenta um: Yₓ = 2Yₓ₋₁ + 1. Isso produz 1, 3, 7, 15 e assim por diante.

A expressão que segue esse padrão é Y = 2^X − 1, alternativa A. Substituindo X de um a quatro, reproduzimos todos os valores da tabela.

Estude com a MMI

Matemática e Física com direção.

Conheça os cursos com Ramon Siqueira e os materiais para a sua preparação.

Resolução MMIAtualizado em 07/11/2026