Can All Bulbs Be On?

Discrete Mathematics Level 4

Let \(n\) be a positive integer \(\leq 1000.\) Suppose \(n\) 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.\)

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...