(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
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
.
(a) De quantas maneiras diferentes o sapo pode chegar da pedra
(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
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
) e quer chegar até a pedra numerada . As pedras estão em linha e numeradas .\n - Em cada movimento o sapo pode: pular 1 pedra (avanço de
) ou pular 2 pedras (avanço de ).\n
O enunciado faz três pedidos claros:\n
(a) Calcular explicitamente o número de maneiras diferentes de chegar quando.\n
(b) Determinar uma fórmula ou relação de recorrência para o número de caminhos até a pedra.\n
(c) Calcular explicitamente o número de maneiras quando.\n
Informações importantes dadas: os únicos passos possíveis têm tamanhoou . 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
= número de maneiras que o sapo tem de chegar à pedra partindo da beirada (posição ).\n - Explicando a ideia por trás da contagem: para chegar em
, o último salto do sapo foi ou de (ou seja, veio de ) ou de (veio de ). 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é é a soma das maneiras de chegar em (e então pular 1) com as maneiras de chegar em (e então pular 2).\n - Isso nos sugere a relação entre os
. 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
:
- Agora precisamos das condições iniciais (casos mais pequenos que iniciam a recorrência):\n
- Para
: só há uma possibilidade — o sapo dá um salto de direto da beirada para a pedra . Logo
- Para
: há duas possibilidades — ou dois saltos de ( ) ou um salto de . Logo
- Para
- Observação didática: às vezes é útil definir
(uma maneira de “ficar” na beira), porque então a fórmula vale também para se quisermos. Mas aqui já fixamos e diretamente, que é suficiente.
Passo 4
Calcular explicitamente
usando a recorrência (resolvendo o item (a))\n
- Já sabemos
e .\n - Para
:
Interpretação prática: as sequências de saltos que dão
são
— exatamente 3.\n
- Para
:
Exemplos de sequências para
:
.\n
- Para
:
Então as respostas pedidas no item (a) são
para
, 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
, suponha que o sapo faz exatamente saltos de tamanho . Então o total de saltos será (de tamanho 2) mais (saltos de tamanho 1), totalizando saltos. Desses “lugares” de salto, escolhemos quais serão os saltos de tamanho . Assim, para cada válido (isto é, ) há
sequências distintas. Somando sobre todos os
possíveis obtemos a fórmula
- 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
são os números de Fibonacci “deslocados”: se a sequência de Fibonacci for . Não é obrigatório usar essa forma, mas é uma conexão útil.\n - Pequeno exemplo de verificação para
usando a soma: , termos : , que confere com .
Passo 6
Cálculo explícito de
(item (c)), duas verificações: recorrência e soma binomial\n
- Usando a recorrência e os valores já calculados:
- Verificação rápida pela soma de binomiais:
Calculando os termos:
confirma
.\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.
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)
\n
(b) com
. Alternativamente
.\n
(c)
(b)
(c)