PRÁTICA COM QUESTÕES OFICIAIS

Questão 171 do ENEM PPL 2011

2º dia · Matemática · Matemática: Sequências e padrões

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.

Ilustração do jogo Torre de Hanói com três hastes verticais sobre uma base horizontal, identificadas como Casas A, B e C. Na haste A, encontram-se empilhadas cinco peças numeradas de 1 a 5 (da maior para a menor, de baixo para cima); as hastes B e C estão vazias.

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) é

  1. A
    Y = 2^X - 1
  2. B
    Y = 2^{X - 1}
  3. C
    Y = 2^X
  4. D
    Y = 2X - 1
  5. E
    Y = 2X - 4
Escolha uma alternativa para conferir o gabarito.
Reportar erro na questão
O que está errado?
Sem cadastro: não guardamos quem enviou.
Resolução comentada

Os valores de Y da tabela são 1, 3, 7, 15. Cada um deles está uma unidade abaixo de uma potência de 2: 2, 4, 8, 16. Isso sugere Y = 2^X - 1.

Para confirmar, teste a fórmula em cada linha da tabela:

  1. X = 1: 2^1 - 1 = 1 ✓
  2. X = 2: 2^2 - 1 = 3 ✓
  3. X = 3: 2^3 - 1 = 7 ✓
  4. X = 4: 2^4 - 1 = 15 ✓

A fórmula vale nas quatro linhas. Ela também tem sentido no jogo. Para mover X discos, primeiro movem-se os X-1 menores para outra haste, o que custa Y_{X-1} movimentos. Depois move-se o maior disco, com 1 movimento. Por fim, movem-se de novo os X-1 menores, com mais Y_{X-1} movimentos. Assim, Y_X = 2Y_{X-1} + 1. Por exemplo, 2\cdot 7 + 1 = 15.

As outras alternativas falham já nos primeiros valores. A (B) dá Y=1 para X=2, e a (D) dá Y=5 para X=3.

Alternativa A.

Por que as outras alternativas estão erradas

  • B2^{X-1} dá 1, 2, 4, 8, que não coincidem com 3, 7, 15 da tabela.
  • C2^X dá 2, 4, 8, 16, sempre uma unidade a mais que a tabela; esqueceu o -1.
  • D2X-1 é função afim e dá 3 para X=2, mas 5 para X=3, não 7.
  • E2X-4 dá -2 para X=1, valor negativo que não bate com a tabela.

Assuntos: Sequências e padrões, Função exponencial.

Reportar erro na resolução
O que está errado?
Sem cadastro: não guardamos quem enviou.
Ver como caiu na prova Questão 171 no caderno Cinza do ENEM PPL 2011