Problema 6 · Els salts del cangur
Una recurrència tipus Fibonacci: $f(n) = f(n-1) + f(n-3)$.
Resposta entera de 4 xifres com a màximUn cangur es mou sobre una línia recta fent salts endavant, que poden ser d'un metre o de tres metres. Si es vol moure exactament 10 metres, de quantes maneres diferents ho pot fer? (Considereu que la mateixa combinació de salts en diferent ordre són maneres diferents de saltar; per exemple, la seqüència $\{3,3,3,1\}$ i la $\{1,3,3,3\}$ són maneres diferents).
Copa Cangur · SCM
Mitjana
Resposta tancada
Solució raonada
Idea clau: sigui $f(n)$ el nombre de maneres d'avançar $n$ metres. L'últim salt és d'$1$ o de $3$ metres: $f(n) = f(n-1) + f(n-3)$.
Amb $f(0) = f(1) = f(2) = 1$ (només uns):
$$f(3)=2,\ f(4)=3,\ f(5)=4,\ f(6)=6,\ f(7)=9,\ f(8)=13,\ f(9)=19,\ f(10)=28.$$
Resposta: 28