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 .
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á
pedras em linha, numeradas sequencialmente de
a
. Saltitante começa na pedra
e quer chegar à pedra
. A cada salto ele pode avançar
,
ou
pedras (isto é, de uma pedra
ele pode ir para
,
ou
). 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:
. Das propriedades desses números, os que são primos (peguei essa informação calculando os primos entre
e
) são
. Pergunta que precisamos responder: qual o número de sequências diferentes de saltos que levam Saltitante de
a
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
, o número de maneiras de chegar nela a partir da pedra
, obedecendo às regras. Seja
o número de sequências de saltos que terminam exatamente na pedra de número
. Por que isso funciona? Porque qualquer caminho que termine em
chega à pedra
vindo de uma das três pedras anteriores:
(com um salto de tamanho
),
(salto
) ou
(salto
). Logo, se não há restrições, vale a recorrência
pois as maneiras de chegar em
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
quando
é 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
, então há exatamente uma maneira de estar na pedra
no começo (a configuração inicial), ou seja
Para qualquer pedra cujo número é primo (aqui
) temos
Para índices menores que
(como
) não consideramos caminhos, então tomamos implicitamente
para
. Com isso, podemos aplicar a recorrência para cada
de
até
.
Passo 4
Calcule
. Como
é primo (pedra contaminada), por regra temos
Passo 5
Calcule
. Aplicando a recorrência e lembrando que
(fora do intervalo) e
:
Interpretação: a única forma de chegar em
é pular diretamente de
para
(um salto de comprimento
), porque não podemos pousar em
.
Passo 6
Calcule
. Como
é primo, não é permitido pousar nela, então
Passo 7
Calcule
. Use a recorrência com os valores já obtidos:
Interpretação: o único caminho para
é chegar em
(que tem
forma) e pular
pedras até
; não dá para vir de
(proibida) nem de
(proibida).
Passo 8
Calcule
:
Interpretação: há duas sequências que chegam a
: (i) ir
e (ii) ir
(salto de
de
para
), por exemplo — as combinações concretas vêm das maneiras de chegar em
e em
.
Passo 9
Calcule
:
Interpretação: as
maneiras vêm de todos os caminhos que terminam em
(e saltam
), em
(saltam
) ou em
(impossível, pois
).
Passo 10
Calcule
. Como
é primo, temos
Passo 11
Calcule
, que é o nosso objetivo (número de sequências que terminam exatamente em
):
Portanto, contando todos os caminhos possíveis com saltos de
,
ou
que nunca pousam em pedras primos (
), obtemos
sequências distintas.
Resposta
(A)