(In reply to How problem was modified
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