Questão 6 (Nível 2) da 2ª fase da OBMEP 2014

Resolução comentada

a) Se o primeiro movimento é 1\to2, o resto é igual a uma brincadeira em 4 degraus (2, 3, 4, 5), que tem 4 maneiras. Se o primeiro movimento é 1\to3, só há duas possibilidades: 1\text{-}3\text{-}2\text{-}4\text{-}5 e 1\text{-}3\text{-}5\text{-}4\text{-}2. As seis maneiras são:

1. 1-2-3-4-5
2. 1-2-3-5-4
3. 1-2-4-3-5
4. 1-2-4-5-3
5. 1-3-2-4-5
6. 1-3-5-4-2

As seis maneiras são as listadas acima.

b) Basta mostrar um caminho que termina no degrau 2. Suba de dois em dois pelos degraus ímpares: 1\to3\to5\to\cdots. Ao chegar no topo, passe para o degrau par vizinho (um degrau a mais ou a menos, conforme n seja par ou ímpar). Depois desça de dois em dois pelos pares até o 2.

• Se n é par: 1\text{-}3\text{-}\cdots\text{-}(n-1)\text{-}n\text{-}(n-2)\text{-}\cdots\text{-}4\text{-}2.
• Se n é ímpar: 1\text{-}3\text{-}\cdots\text{-}n\text{-}(n-1)\text{-}(n-3)\text{-}\cdots\text{-}4\text{-}2.

Cada degrau é pisado uma única vez e todo movimento é de 1 ou 2 degraus. Para n=2 o caminho é simplesmente 1-2. Logo sempre dá para terminar no degrau 2.

Sempre é possível: o caminho que sobe pelos ímpares e desce pelos pares termina no degrau 2.

c) Seja a_n o número de maneiras com n degraus. Vamos contar de acordo com os primeiros movimentos, para n\ge5.

• Começa com 1\to2: o restante é uma brincadeira nos degraus 2 a n, ou seja, em n-1 degraus. São a_{n-1} maneiras.
• Começa com 1\to3\to2: o único movimento possível depois é 2\to4. O restante é uma brincadeira nos degraus 4 a n, ou seja, em n-3 degraus. São a_{n-3} maneiras.
• Começa com 1\to3 sem passar logo pelo 2: o degrau 2 só tem o 4 como vizinho livre, então ele precisa ser o último, vindo do 4. Um raciocínio parecido mostra que o caminho é forçado a subir pelos ímpares até o topo e descer pelos pares. Se em algum ponto ele não subisse, o degrau par seguinte ficaria inacessível ou o caminho ficaria preso embaixo, deixando degraus acima sem visitar. Portanto há apenas 1 maneira.

Assim, a_n=a_{n-1}+a_{n-3}+1.

Testando: a_1=1,\ a_2=1,\ a_3=2,\ a_4=4,\ a_5=4+1+1=6, o que confere com o item (a).

Continuando:

1. a_6=6+2+1=9
2. a_7=9+4+1=14
3. a_8=14+6+1=21
4. a_9=21+9+1=31 (confere com o enunciado)
5. a_{10}=31+14+1=46
6. a_{11}=46+21+1=68 (confere com o enunciado)
7. a_{12}=a_{11}+a_9+1=68+31+1=100

Fábio pode brincar de 100 maneiras diferentes.

Assuntos: Princípio fundamental da contagem, Sequências e padrões.

Reportar erro na resolução

O que está errado?

Conta ou raciocínio errado Chega em outra resposta Explicação confusa Outro problema

Detalhes (opcional) Não preencha

Enviar Sem cadastro: não guardamos quem enviou.