Problema 6 · Las seis cámaras
Cadenas sin dos ceros seguidos: Fibonacci escondido.
Respuesta entera de 4 cifras como máximoSeis cámaras se han alineado a lo largo de un camino de entrada. Queremos encender unas cuantas de estas cámaras (también pueden ser todas) de manera que no haya dos (o más) cámaras adyacentes apagadas. ¿De cuántas maneras diferentes lo podemos hacer?
Copa Cangur · SCM
Media
Respuesta cerrada
Solución razonada
Idea clave: sea $g(n)$ el número de configuraciones válidas para $n$ cámaras. Miramos la última: si está encendida, queda $g(n-1)$; si está apagada, la anterior ha de estar encendida y 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.$$
Respuesta: 21