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 How problem was modified by Bractals)

This is helpful. It is clear that 2^n+1 will never be all off, given that for 2^n will eventually be off. Note since the only two states which lead to all off are all off or all on, it follows on the stage before they are all off (cal this stage g), the lights must all be on.

Thus, by a constructive argument, similar to Dej Mar's post it follows, on stage g for 2^n+1 lamps, they are all on except the last one. The next stage will thus be all off except the last two, which will repeat the second stage.

(Thus, the lamps will repeat the process, except right to left. When finished, they will repeat the whole process again, thus never be off.)

I think it's reasonable to wonder if this happens in the hard cases as well as the easy cases.

Posted by Gamer on 2010-09-04 02:53:27