Há 9 pedras igualmente espaçadas em linha reta e numeradas sequencialmente com os números inteiros de 10 a 18.
O sapinho Saltitante está sobre a pedra de número 10 e deseja ir para a pedra de número 18. A cada salto, Saltitante pode pular 1, 2 ou 3 pedras na direção da pedra de número 18. Entretanto, as pedras que têm números primos estão contaminadas com um veneno mortal e Saltitante tem que evitá-las.
O número de sequências diferentes de saltos que Saltitante pode executar para ir da pedra de número 10 à pedra de número 18 é:
(A) 5 ;
(B) 6 ;
(C) 7 ;
(D) 8 ;
(E) 9 .

Passo 1

O enunciado dá as seguintes informações: há 9 pedras em linha, numeradas sequencialmente de \,10 a \,18. Saltitante começa na pedra \,10 e quer chegar à pedra \,18. A cada salto ele pode avançar 1, 2 ou 3 pedras (isto é, de uma pedra n ele pode ir para n+1, n+2 ou n+3). As pedras cujo número é primo estão contaminadas e Saltitante não pode ficar em cima delas (não pode pousar nelas). Do enunciado extraímos explicitamente os números das pedras: \,10,11,12,13,14,15,16,17,18. Das propriedades desses números, os que são primos (peguei essa informação calculando os primos entre \,10 e \,18) são \,11,\;13,\;17. Pergunta que precisamos responder: qual o número de sequências diferentes de saltos que levam Saltitante de \,10 a \,18 sem pousar em pedras primas?

Passo 2

Estratégia e ideia chave (explicação passo a passo do raciocínio que você deve aprender para a prova). Vamos modelar o problema contando, para cada pedra n, o número de maneiras de chegar nela a partir da pedra \,10, obedecendo às regras. Seja a(n) o número de sequências de saltos que terminam exatamente na pedra de número n. Por que isso funciona? Porque qualquer caminho que termine em n chega à pedra n vindo de uma das três pedras anteriores: n-1 (com um salto de tamanho 1), n-2 (salto 2) ou n-3 (salto 3). Logo, se não há restrições, vale a recorrência
a(n)=a(n-1)+a(n-2)+a(n-3),
pois as maneiras de chegar em n são exatamente as maneiras de chegar em cada uma das pedrasa anteriores e então dar o salto final. Agora, como há pedras proibidas (primas), simplesmente fixamos a(n)=0 quando n é primo (porque não é permitido terminar um salto em pedra prima). Essa é uma aplicação simples de programação dinâmica / recorrência: dividir o problema em subproblemas menores (número de maneiras de chegar em pedras anteriores) e somá-los.

Passo 3

Condições iniciais e detalhes de contorno (o que usar como sementes da recorrência). Saltitante começa em \,10, então há exatamente uma maneira de estar na pedra \,10 no começo (a configuração inicial), ou seja
a(10)=1.
Para qualquer pedra cujo número é primo (aqui \,11,\;13,\;17) temos
a(11)=a(13)=a(17)=0.
Para índices menores que \,10 (como \,9,\;8,\ldots) não consideramos caminhos, então tomamos implicitamente a(n)=0 para n<10. Com isso, podemos aplicar a recorrência para cada n de \,11 até \,18.

Passo 4

Calcule a(11). Como \,11 é primo (pedra contaminada), por regra temos
a(11)=0.

Passo 5

Calcule a(12). Aplicando a recorrência e lembrando que a(9)=0 (fora do intervalo) e a(11)=0:
a(12)=a(11)+a(10)+a(9)=0+1+0=1.
Interpretação: a única forma de chegar em \,12 é pular diretamente de \,10 para \,12 (um salto de comprimento 2), porque não podemos pousar em \,11.

Passo 6

Calcule a(13). Como \,13 é primo, não é permitido pousar nela, então
a(13)=0.

Passo 7

Calcule a(14). Use a recorrência com os valores já obtidos:
a(14)=a(13)+a(12)+a(11)=0+1+0=1.
Interpretação: o único caminho para \,14 é chegar em \,12 (que tem 1 forma) e pular 2 pedras até \,14; não dá para vir de \,13 (proibida) nem de \,11 (proibida).

Passo 8

Calcule a(15):
a(15)=a(14)+a(13)+a(12)=1+0+1=2.
Interpretação: há duas sequências que chegam a \,15: (i) ir \,10\to12\to14\to15 e (ii) ir \,10\to12\to15 (salto de 3 de \,12 para \,15), por exemplo — as combinações concretas vêm das maneiras de chegar em \,12 e em \,14.

Passo 9

Calcule a(16):
a(16)=a(15)+a(14)+a(13)=2+1+0=3.
Interpretação: as 3 maneiras vêm de todos os caminhos que terminam em \,15 (e saltam 1), em \,14 (saltam 2) ou em \,13 (impossível, pois 0).

Passo 10

Calcule a(17). Como \,17 é primo, temos
a(17)=0.

Passo 11

Calcule a(18), que é o nosso objetivo (número de sequências que terminam exatamente em \,18):
a(18)=a(17)+a(16)+a(15)=0+3+2=5.
Portanto, contando todos os caminhos possíveis com saltos de 1, 2 ou 3 que nunca pousam em pedras primos ( \,11,13,17), obtemos 5 sequências distintas.

Resposta

(A) 5

Exercícios relacionados