All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Lamps in a row (Posted on 2010-09-03)
There are n ≥ 2 lamps L1, L2, ..., Ln in a row. Each of them is
either on or off. Initially L1 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 (L1 and Ln 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 47th IMO in Slovenia 2006.

 No Solution Yet Submitted by Bractals No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Almost proved: two gaps | Comment 5 of 11 |
(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

 Search: Search body:
Forums (0)