Problema 6 · Les sis càmeres
Cadenes sense dos zeros seguits: Fibonacci amagat.
Resposta entera de 4 xifres com a màximSis càmeres s'han alineat al llarg d'un camí d'entrada. Volem encendre unes quantes d'aquestes càmeres (també poden ser totes) de manera que no hi hagi dues (o més) càmeres adjacents apagades. De quantes maneres diferents ho podem fer?
Copa Cangur · SCM
Mitjana
Resposta tancada
Solució raonada
Idea clau: sigui $g(n)$ el nombre de configuracions vàlides per a $n$ càmeres. Mirem l'última: si està encesa, queda $g(n-1)$; si està apagada, l'anterior ha d'estar encesa i queda $g(n-2)$.
$$g(n) = g(n-1) + g(n-2), \qquad g(1) = 2,\ g(2) = 3.$$
$$g(3) = 5,\ g(4) = 8,\ g(5) = 13,\ g(6) = 21.$$
Resposta: 21