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 solution by Dej Mar)

The pattern has a three important features:
First on an arbitrarily long string of lamps at every phase 2^n - 1 there is a single string of on lamps.  This only happens at phase numbered by powers of 2. [this needs proving]

Second, the highest number of lit lamp is one more than the phase number.  ie at phase 0 lamp L1 is lit, at phase 1 lamp L2 is lit etc...
[proof: L(a) will light the phase after L(a-1) since it is at a different state]

Third, only way the lamps can all turn off is if they all turn on.
[proof: this is the only way they call all be the same state.]

So if n is a power of two then on phase n-1 the lights will all be on and on phase n they will all turn off.

If n is not a power of two, then on phase n-1 when the last light is lit they are not all lit.  So they will not all turn off on phase n.  

[What I thought I had shown was phase n would be a repeat of a previous phase or a repeat in reversed order.  This is not the case.  Proving a repeat eventually occurs this will be necessary.]

Posted by Jer on 2010-09-03 15:34:40