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: How problem was modified | Comment 9 of 11 |
(In reply to How problem was modified by Bractals)

This is helpful. It is clear that 2^n+1 will never be all off, given that for 2^n will eventually be off. Note since the only two states which lead to all off are all off or all on, it follows on the stage before they are all off (cal this stage g), the lights must all be on.

Thus, by a constructive argument, similar to Dej Mar's post it follows, on stage g for 2^n+1 lamps, they are all on except the last one. The next stage will thus be all off except the last two, which will repeat the second stage.

(Thus, the lamps will repeat the process, except right to left. When finished, they will repeat the whole process again, thus never be off.)

I think it's reasonable to wonder if this happens in the hard cases as well as the easy cases.

 Posted by Gamer on 2010-09-04 02:53:27

 Search: Search body:
Forums (0)