ENEM 2011 · PPL · Questão 171

Matemática e suas Tecnologias · Dada uma situação-problema, determine a função exponencial

Dificuldade TRI: b = 2,21 (média)

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.

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$

Ver a resposta e a resolução

Resposta: A

Resposta: (A) $Y=2^X-1$ .

A ideia: a quantidade mínima de movimentos quase dobra a cada disco adicional: o novo total é o dobro do anterior mais um.

Resolução. A tabela fornece os pares $(1,1)$ , $(2,3)$ , $(3,7)$ e $(4,15)$ . Observe que $3=2\cdot1+1$ , $7=2\cdot3+1$ e $15=2\cdot7+1$ . Isso ocorre porque, para deslocar uma torre de $X$ discos, é preciso mover os $X-1$ menores para a haste auxiliar, transferir o maior uma vez e mover novamente os $X-1$ menores: $Y_X=2Y_{X-1}+1$ . A fórmula $Y=2^X-1$ satisfaz a recorrência e todos os valores: para $X=4$ , $2^4-1=15$ .

Visualize: Hanói: dobrar o total e somar um. Discos X, Movimentos Y. Y = 2ˣ − 1; regra Y seguinte = 2Y + 1

Construção auxiliar de enem-2011ppl-q171

Onde a galera erra: a alternativa C, $2^X$ , esquece subtrair uma unidade e já falha para um único disco.

Leve para a prova: reconheça uma recorrência simples e valide a fórmula candidata nos primeiros termos.

Vai fazer o ENEM?

O Impulso ENEM ensina a reconhecer os padrões que mais caem na prova de Matemática, com questões reais e a dificuldade de cada uma pela TRI. Me chama que eu te conto como funciona.

Falar com o Thiago