(5 pontos) Um sapo deseja passear por um lago pulando sobre pedras alinhadas. Inicialmente ele está na beirada do lado e quer chegar à última pedra.
Em cada movimento o sapo pode:
  • pular para a próxima pedra (avançando 1 pedra), ou
  • pular duas pedras de uma vez (avançando 2 pedras).
    (a) De quantas maneiras diferentes o sapo pode chegar da pedra n=1,2,3,4 e 5
    (b) Determine uma fórmula ou relação de recorrência para esse número de caminhos.
    (c) Calcule explicitamente o número de maneiras quando n=10.

Passo 1

O que o enunciado pede e o que ele nos dá\n
  • O sapo começa na beirada (chamo isso de posição inicial 0) e quer chegar até a pedra numerada n. As pedras estão em linha e numeradas 1,2,\dots,n.\n
  • Em cada movimento o sapo pode: pular 1 pedra (avanço de 1) ou pular 2 pedras (avanço de 2).\n
    O enunciado faz três pedidos claros:\n
    (a) Calcular explicitamente o número de maneiras diferentes de chegar quando n=1,2,3,4,5.\n
    (b) Determinar uma fórmula ou relação de recorrência para o número de caminhos até a pedra n.\n
    (c) Calcular explicitamente o número de maneiras quando n=10.\n
    Informações importantes dadas: os únicos passos possíveis têm tamanho 1 ou 2. Nada mais foi omitido.

Passo 2

Modelagem e definição de variável (passo importante para organizar a solução)\n
  • Defino a quantidade procurada por a_n = número de maneiras que o sapo tem de chegar à pedra n partindo da beirada (posição 0).\n
  • Explicando a ideia por trás da contagem: para chegar em n, o último salto do sapo foi ou de 1 (ou seja, veio de n-1) ou de 2 (veio de n-2). Esses dois casos são disjuntos (não acontecem ao mesmo tempo) e cobrem todas as possibilidades. Então o número total de caminhos até n é a soma das maneiras de chegar em n-1 (e então pular 1) com as maneiras de chegar em n-2 (e então pular 2).\n
  • Isso nos sugere a relação entre os a_n. Vou formalizar já no próximo passo.

Passo 3

Obter a relação de recorrência e as condições iniciais (a parte teórica necessária)\n
  • Pela ideia do último salto temos, para todo n\ge3:
a_n = a_{n-1} + a_{n-2}.
  • Agora precisamos das condições iniciais (casos mais pequenos que iniciam a recorrência):\n
    • Para n=1: só há uma possibilidade — o sapo dá um salto de 1 direto da beirada para a pedra 1. Logo
    a_1 = 1.
    • Para n=2: há duas possibilidades — ou dois saltos de 1 ( 1+1) ou um salto de 2. Logo
    a_2 = 2.
  • Observação didática: às vezes é útil definir a_0=1 (uma maneira de “ficar” na beira), porque então a fórmula a_n=a_{n-1}+a_{n-2} vale também para n=2 se quisermos. Mas aqui já fixamos a_1 e a_2 diretamente, que é suficiente.

Passo 4

Calcular explicitamente a_1,\dots,a_5 usando a recorrência (resolvendo o item (a))\n
  • Já sabemos \;a_1=1 e \;a_2=2.\n
  • Para n=3:
a_3 = a_2 + a_1 = 2 + 1 = 3.
Interpretação prática: as sequências de saltos que dão 3 são (1,1,1), (1,2), (2,1) — exatamente 3.\n
  • Para n=4:
a_4 = a_3 + a_2 = 3 + 2 = 5.
Exemplos de sequências para 4: (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2).\n
  • Para n=5:
a_5 = a_4 + a_3 = 5 + 3 = 8.
Então as respostas pedidas no item (a) são 1,2,3,5,8 para n=1,2,3,4,5, respectivamente.

Passo 5

Outra fórmula fechada (combintorial) e conexão com Fibonacci — útil para prova e verificação\n
  • Explicação combinatorial: para um determinado n, suponha que o sapo faz exatamente k saltos de tamanho 2. Então o total de saltos será k (de tamanho 2) mais n-2k (saltos de tamanho 1), totalizando n-k saltos. Desses n-k “lugares” de salto, escolhemos quais k serão os saltos de tamanho 2. Assim, para cada k válido (isto é, 0\le k\le\lfloor n/2\rfloor) há
\binom{n-k}{k}
sequências distintas. Somando sobre todos os k possíveis obtemos a fórmula
a_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}.
  • Isso é uma fórmula fechada em termos de somatório de binomiais e é equivalente à recorrência anterior. Também vale mencionar (se alguém perguntar numa prova) que esses números a_n são os números de Fibonacci “deslocados”: \,a_n=F_{n+1} se a sequência de Fibonacci F_1,F_2,\dots for 1,1,2,3,\dots. Não é obrigatório usar essa forma, mas é uma conexão útil.\n
  • Pequeno exemplo de verificação para n=4 usando a soma: \lfloor4/2\rfloor=2, termos k=0,1,2: \binom{4}{0}+\binom{3}{1}+\binom{2}{2}=1+3+1=5, que confere com a_4=5.

Passo 6

Cálculo explícito de a_{10} (item (c)), duas verificações: recorrência e soma binomial\n
  • Usando a recorrência e os valores já calculados:
\begin{aligned} a_6 &= a_5 + a_4 = 8 + 5 = 13,\\\ a_7 &= a_6 + a_5 = 13 + 8 = 21,\\\ a_8 &= a_7 + a_6 = 21 + 13 = 34,\\\ a_9 &= a_8 + a_7 = 34 + 21 = 55,\\\ a_{10} &= a_9 + a_8 = 55 + 34 = 89. \end{aligned}
  • Verificação rápida pela soma de binomiais:
a_{10}=\sum_{k=0}^{5}\binom{10-k}{k} =\binom{10}{0}+\binom{9}{1}+\binom{8}{2}+\binom{7}{3}+\binom{6}{4}+\binom{5}{5}.
Calculando os termos:
1 + 9 + 28 + 35 + 15 + 1 = 89,
confirma a_{10}=89.\n
Boa notícia: dá para fazer esse cálculo à mão em pouco tempo (só somas e alguns binomiais simples), o que é ideal para uma prova sem calculadora.

Resposta

(a) \;a_1=1,\\ a_2=2,\\ a_3=3,\\ a_4=5,\\ a_5=8\n
(b) \;a_n=a_{n-1}+a_{n-2} com \;a_1=1,\\ a_2=2. Alternativamente \;a_n=\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}.\n
(c) \;a_{10}=89

Exercícios relacionados