PRÁTICA COM QUESTÕES OFICIAIS
Questão 5 (Nível 3) da 2ª fase da OBMEP 2014
Fábio gosta de brincar em escadas, subindo ou descendo seus degraus da seguinte maneira:
• começa no degrau de número 1;
• a cada movimento ele sobe ou desce um ou dois degraus e, ao subir ou descer dois degraus, não pisa no degrau intermediário;
• pisa em todos os degraus exatamente uma vez.
Por exemplo, em uma escada com três degraus ele pode brincar de duas maneiras diferentes: 1-2-3, 1-3-2; com quatro degraus ele pode brincar de quatro maneiras diferentes: 1-2-3-4, 1-2-4-3, 1-3-2-4 e 1-3-4-2.
a) Fábio pode brincar de seis maneiras diferentes em uma escada com cinco degraus. Escreva essas seis maneiras.
b) Explique por que sempre é possível terminar a brincadeira no degrau de número 2 em qualquer escada com dois ou mais degraus.
c) Há 31 e 68 maneiras diferentes de se brincar em escadas com nove e onze degraus, respectivamente. De quantas maneiras diferentes Fábio pode brincar em uma escada com doze degraus?
Reportar erro na questão
Resolução comentada
Resolução comentada
a) Vamos listar os caminhos pelo segundo degrau.
Se Fábio vai de 1 para 2, o que falta é um caminho que parte do 2 e passa por 3, 4 e 5. Isso é o mesmo que a escada de 4 degraus, que tem 4 maneiras:
- 1-2-3-4-5
- 1-2-3-5-4
- 1-2-4-3-5
- 1-2-4-5-3
Se ele vai de 1 para 3, o degrau 2 só pode ser visitado depois, vindo do 3 ou do 4 (o 1 já foi usado). Há duas possibilidades:
- 1-3-2 e depois 4-5, o que dá 1-3-2-4-5;
- 1-3-5-4-2. Aqui o 2 fica por último, vindo do 4, e o 5 precisa vir antes do 4.
O caminho 1-3-4-... não serve com 5 degraus, porque o 2 ficaria sem como ser visitado.
As seis maneiras são: 1-2-3-4-5, 1-2-3-5-4, 1-2-4-3-5, 1-2-4-5-3, 1-3-2-4-5 e 1-3-5-4-2.
b) Basta mostrar um caminho que sempre termina no 2.
Suba pelos degraus ímpares: 1,3,5,\dots até o maior ímpar que cabe na escada. Depois dê um passo de 1 degrau para chegar ao topo, ou ao degrau n se ele for par. Em seguida, desça de 2 em 2 pelos pares até o 2.
- Se n é par: 1-3-5-\dots-(n-1)-n-(n-2)-\dots-4-2.
- Se n é ímpar: 1-3-5-\dots-n-(n-1)-(n-3)-\dots-4-2.
Todos os degraus são pisados uma única vez (ímpares na subida, pares na descida), e cada movimento é de 1 ou 2 degraus. Para n=2, o caminho é simplesmente 1-2. Logo, é sempre possível terminar no degrau 2.
c) Seja a_n o número de maneiras com n degraus. Vamos separar os caminhos pelo início.
- Começa com 1-2: sobra um caminho que parte do 2 e percorre os n-1 degraus de 2 a n. São a_{n-1} maneiras.
- Começa com 1-3-2: o próximo degrau é obrigatoriamente o 4. Sobra um caminho que parte do 4 e percorre os n-3 degraus de 4 a n. São a_{n-3} maneiras.
- Começa com 1-3 e não visita o 2 em seguida: o 2 só pode ser alcançado a partir do 4, então ele é o último degrau. Isso força o caminho da letra b, que sobe pelos ímpares e desce pelos pares. É apenas 1 maneira.
Portanto a_n=a_{n-1}+a_{n-3}+1.
Conferindo com os dados: a_4=2+1+1=4 e a_5=4+1+1=6, como no enunciado.
Calculando em sequência:
- a_6=6+2+1=9
- a_7=9+4+1=14
- a_8=14+6+1=21
- a_9=21+9+1=31 (confere com o enunciado)
- a_{10}=31+14+1=46
- a_{11}=46+21+1=68 (confere com o enunciado)
- a_{12}=68+31+1=100
Fábio pode brincar de 100 maneiras diferentes.
Assuntos: Sequências e padrões, Princípio fundamental da contagem.
Reportar erro na resolução
Esta questão também caiu em
Ver como caiu na prova
Fonte: OBMEP 2ª fase 2014 · Nível 3. Prova oficial ↗