There are 29 light bulbs in a garland, each one may or may not be lit. What is the largest possible number
There are 29 light bulbs in a garland, each one may or may not be lit. What is the largest possible number of different states a garland can have if two adjacent bulbs cannot be turned off in it? For example, a garland of two light bulbs has three possible states: both are on; the first is on and the second is off; the first is off and the second is on.
For example, suppose there are n lights in a garland, it is necessary to designate the off light as 0 and on as 1. We need to find the number f (n) of possible garlands for which two zeros will not go in a row. Based on this, f1 = 2 and f2 = 3, provided that n> = 3. The states of the paws end in either 1 or 10, and before that the state of the garland is written, the length of which is n-1 or n-2, where two zeros do not occur.
Therefore, here it is necessary to apply the recurrent formula f (n) = f (n-1) + f (n-2) for n> = 3.
It follows that these are Fibonacci numbers, i.e. each next is equal to the sum of the two previous ones. We calculate the number 31, it is equal to 3524578