Problem 6 · The six cameras
Strings with no two adjacent zeros: hidden Fibonacci.
Integer answer, at most 4 digitsSix cameras are lined up along a driveway. We want to switch on some of them (possibly all) so that no two (or more) adjacent cameras are off. In how many different ways can we do this?
Copa Cangur · SCM
Medium
Closed answer
Reasoned solution
Key idea: let $g(n)$ be the number of valid configurations for $n$ cameras. Look at the last one: if it is on, $g(n-1)$ remain; if it is off, the previous one must be on, leaving $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.$$
Answer: 21