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.)
 re: Almost proved: two gaps | Comment 6 of 11 |
(In reply to Almost proved: two gaps by Jer)

I ran it on a computer with n=149 and 1000 state changes.

The pattern in the 149 lamps did not repeat in either the forward order or the reverse order.

The pattern when you look at a two dimensional view is beautiful, except when the pattern from one end of the row runs into the pattern from the other end.

If one can prove that this chaotic pattern cannot produce a row with all the lamps on, I would really like to see it.

 Posted by Bractals on 2010-09-03 20:10:34

 Search: Search body:
Forums (0)