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.

I suggest the following approach:

Make a table with 4 lamps, L1,L2,L3,L4..., across the top. Number down the side, 0,1,2,3.... We shall note two features; whether the lamp is on or off ( best done with colours, here on is shown in bold) and whether its status has changed or not. For convenience we assume that the status of lamp 1 has just changed (C) at time 0; the status of all other lamps is the same (S).

When n is a power of 2, there are exactly 6 possible blocks which collectively tile the whole table:

Leading edge:

1.       CS

2.       SC

Leading edge reversed:

1.       SC

2.       CS

Trailing edge:

1.       CS

2.       CS

Trailing edge reversed:

1.       SC

2.       SC

Empty (all off):

1.       SS

2.       SS

Transition (all off):

1.       CC

2.       SS

When n is a power of 2, the blocks in the n-1th row will be: Leading reversed/Trailing reversed – Trailing/leading – Leading reversed/Trailing reversed – etc, for a pattern (all switched on) of CSSCCSSCCSSC..., where L1 and Ln were in the n-2^nd row in the opposite state to their neighbours, and every other lamp was at that time in the same state as one of its neighbours, and the opposite state from the other, this sequence being the only one possible compliant with these requirements. Hence all the lamps switch off together at time n.

When n is a multiple of 2, but not a power of 2, the same component blocks are used, but the sequence is interrupted at the end, because at time n-1 the leading edge of the sequence reaches, and switches on, lamp Ln, but the trailing edge has not yet had time to reach back to L1. This causes the pattern to oscillate back and forth indefinitely.

Let n be odd, and let time x be a time when all the lamps are to be switched on. At time x-1, lamp L1 must be off (if it is on at x-1, this implies that L1 and L2 were in opposite states at x-2, therefore the same state at x-1).  Its state is therefore either C, off or S, off. In either case, the adjacent light L2 was in the same state at x-2, and must now be in the opposite state, C, on. For the lamps all to be switched on, the series must then continue, L3 on, L4 and L5 off, etc.

Now the same reasoning applies to Ln, which must also be off at time x-1. We also know that Ln must be of the opposite state from Ln-1. Since we are dealing with an odd number, the final 3 elements of the sequence must be Ln-2 off, Ln-1 on, Ln off. Ln-2 is the second part of a two man sequence; it must therefore follow that unless n is of the form 4k+1, it will never occur that all lights will be on at the same time.

Now assume that the last 6 lamps are on,on,off, off, on, off at x-1, as required by the foregoing. At x-2, either both Ln and Ln-1 were on, or both of them were off. But in either case, Ln-2 must have been in the opposite state from Ln-3, which however reports at time x-1 that it and both its neighbours were in the same state at x-2, which is a paradox.

Hence, for any odd number, it will never occur that all lights will be on at the same time.

 

Edited on September 6, 2010, 7:16 am

Posted by broll on 2010-09-05 06:22:34