Can All Bulbs Be On?

Probability Level 5

Let nn be a positive integer 1000.\leq 1000. Suppose nn bulbs are arranged in a row. Initially the first bulb is switched on and all other bulbs are switched off. Each second, we change the states of the bulbs according to the following rules:

  • If the state of a bulb is identical to the state of all its neighbors (one neighbor for the bulbs at the edges, two neighbors for the other bulbs), it is switched off.

  • Otherwise, it is switched on.

It turns out that eventually (after a finite amount of time) all bulbs are switched on. Find the largest possible value of n.n.

Details and assumptions

  • The state of a bulb refers to whether it is switched on or off.

  • This problem is inspired by ISL 2006 C1.


Problem Loading...

Note Loading...

Set Loading...