There are n ≥ 2 lamps L₁, L₂, ..., L_n in a row. Each of them is
either on or off. Initially L₁ is on and all of the others are off.
Each second the state of each lamp changes as follows:

if the lamp and its neighbors (L₁ and L_n have one neighbor,
any other lamp has two neighbors) are in the same state,
then it is switched off; otherwise, it is switched on.

Prove or disprove that all of the lamps will eventually be switched off
if and only if n is a power of two.

Note: This is a problem that I modified from one proposed but not used at
the 47^th IMO in Slovenia 2006.

(In reply to Almost proved: two gaps by Jer)

I ran it on a computer with n=149 and 1000 state changes.

The pattern in the 149 lamps did not repeat in either the forward order or the reverse order.

The pattern when you look at a two dimensional view is beautiful, except when the pattern from one end of the row runs into the pattern from the other end.

If one can prove that this chaotic pattern cannot produce a row with all the lamps on, I would really like to see it.

Posted by Bractals on 2010-09-03 20:10:34