Contrib Combo [LAMPS]
by DeathLlama9, Jul 14, 2016, 2:41 AM
Furious Readers wrote:
No posts in three days? It's problem of the day, not problem of the three-day period!
Shiningsunnyday, having noticed this, has asked me to post on his blog. As combo is my only good subject, I will post a combo problem.
2006 ISL C1, France wrote:
We have
lamps
in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp
and its neighbours (only one neighbour for
or
, two neighbours for other
) are in the same state, then
is switched off; – otherwise,
is switched on.
Initially all the lamps are off except the leftmost one which is on.
Prove that there are infinitely many integers
for which all the lamps will eventually be off.
Prove that there are infinitely many integers
for which the lamps will never be all off.








Initially all the lamps are off except the leftmost one which is on.




Part A
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.



We claim that all integers in the form



Base Case:




Inductive Step: We claim that if



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

(iii) If a string of






PROOF (uses i and ii): For all turns before the second, that all of the leftmost





By (iii), a starting string of





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





This finishes our inductive hypothesis, so, as








Part B
(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.
We claim that all odds

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


This post has been edited 2 times. Last edited by shiningsunnyday, Jul 14, 2016, 2:45 AM