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 reversed:
Trailing edge reversed:
Empty (all off):
Transition (all off):
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-2nd 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