For readability's sake, lines of lamps will be denoted as binary strings, where represents a lamp that's turned on and a lamp that's turned off. For example, an on lamp followed by three off lamps would be represented by the string .

We claim that all integers in the form , where is positive, satisfy the desired condition. We seek to prove this by induction on .

Base Case: trivially works ( turns into turns into ).

Inductive Step: We claim that if works, then will also work. Paired with our base case, this will prove that all integers of the form work.

PROOF:

(i) Note that any string of lamps that eventually are all off will be all on the second before they all shut off. Proof: Assume that not all lamps are on the turn before they all shut off. Then there will be an "off" lamp next to an "on" lamp. The next second, both of these lamps will be on, contradiction.

(ii) Also note that in a substring of lamps starting from the leftmost lamp in a string, the lamp furthest right will be the last to turn on, and will only turn on the second all lamps turn on. Proof: Obviously, for the lamp to be on, it must be different from the lamp to its left. This is only possible if the lamp to its left is on, since the first lamp turned on is the lamp that is furthest left.

(iii) If a string of lamps works, then a starting string () of lamps will eventually become a binary string consisting of zeroes, ones, and more zeroes (from left to right (although it really doesn't matter :p)).

PROOF (uses i and ii): For all turns before the second, that all of the leftmost lamps turn on, the rightmost of the leftmost lamps will stay off, as will all of the rightmost lamps (because the th lamp hasn't turned on yet). On this second, the entire left substring of lamps will turn on, while the entire right substring will remain off. The middle two lamps are the only two adjacent lamps that are different in on-off-ness, so they are the only ones that will remain on while every other lamp turns off, proving this lemma.

By (iii), a starting string of lamps will eventually become a binary string consisting of zeroes, ones, and more zeroes. Note that this string is essentially a starting string of n lamps "reflected over the end of the sequence to form two concatenated starting strings of lamps, with one reversed.

Note that from here, we can consider these two concatenated strings separately. Since we've already assumed via the inductive hypothesis that a starting string of lamps will eventually become all s, these two strings will also both become all s, making the entire string of lamps all s. These two strings will not interfere with each other, as, since the entire string starts symmetrical, each side will have an identical pattern, meaning it will change on/off in identical ways, keeping the entire string symmetrical and the two sides the same.

This finishes our inductive hypothesis, so, as works and works if works, we can conclude that all integers that can be expressed in the form , where is a natural number, have the property that a string of one on lamp and off lamps, by the defined operations, will always eventually become a string of lamps that are all off.

(Uses the same binary string notation as above)

We claim that all odds greater than one have the property that the lamps will never all be off.

As above, we note that for all the lamps to be off, they must first must all be on (the second before they all turn off). The proof is given above as (i). However, we can prove by induction that it is impossible for all the lights in a string of lamps with an odd number of lamps (with the starting configuration given) to all be on.

LEMMA: After the first second, the number of lamps that are on in such a string is always even.

PROOF: Assume that there is at least one light on before all of the lamps change and that the number of lamps on is odd. Either all of the "on" lamps are on the sides of the string (e.g. 11011), or there are a number of "blocks" of 1s surrounded by zeroes (e.g. 1001110100110)

In the first case, we consider the "blocks" of "on" lamps on each side of the string. All "on"s but the "on"s closest to the middle of the string will turn "off", and the two "off" lamps touching these "on" lamps will turn on. Since all but two "on" lamps turn on, and only two (an even number) "off" lamps turn on, the parity of the number of "on" lamps remains constant.

In the second case, consider each "block" separately. Once again, at the one-zero contact points, both ones and zeroes will turn into ones, and all ones between two ones will turn into zeroes. Note that ones always become in "blocks" with even numbers of ones (this proof is getting kind of long and tedious so something something margins too small), so the number of ones "within" each former block will always remain even. Since this maintains parity, as does flipping the surrounding two zeroes to ones, the parity of the number of "on" lamps remains constant.

This implies that it is impossible for all the lights in a string of lamps with an odd number of lamps (with the starting configuration given) to all be on, as that would require an odd number of lamps to be on, which we have proven will never happen after the first second.

Therefore, we have proven that for all odd numbers greater than one, a starting configuration of lamps will never become all "off" lamps.