I don't really understand how you proved part (b) my solution for part (b) is basically taking 2^n + 1 and then being like haha it reflects since essentially you start out with the left two on and then you get to the left 2^n on and then you have the right two on and then (the reflection of the above) you get to the right 2^n on and then you get left two on blah blah blah at no point are all of them the same state

Yeah I sort of assumed that they gave us the same statement as they did at MOP, which had part (b) prove that at some point they were all on.

You can furthermore prove that if $ n$ is odd, then the lamps will never be all off. It is easy to see that $ 000\ldots 0$ can only result from $ 111\ldots 1$ or $ 000\ldots 0$ (since if you had both, ones and zeros, then there is at least a $ 01$ or a $ 10$ in the chain which will result in a $ 11$). On the other hand, there will always be an even number of ones in the chain and the ones will furthermore only appear in blocks of even size. Also, the number of zeros between two such blocks is always even. This is also easy to verify; it is true after the first step and afterwards, ones will only result from $ 01$ and $ 10$. Also two such "transitions" (ie $ 10$ or $ 01$) cannot coincide since this would require either a $ 101$ or a $ 010$, both impossible by the induction hypothetis. Hence, the number of ones will be 2 times the number of such "transitions", and they will only appear in $ 11$-blocks. Also, the number of separating zeros between two blocks of ones remains even since the the size of an already existing separating zero-block shrinks by 2 and new separating zero-blocks of the length $ k$ can only result from a block of ones of length $ k+2$ and this is an even number by our assumption. Hence, if there is an even number of ones, there will always be an even number of ones, making it impossible to switch off all lamps for odd $ n$ since switching all lamps off would require all lamps to be switched on, thus an odd number of ones. $ \Box$

Lemma: If we have an infinite sequence of lamps $L_{1},L_{2},....$ we prove by induction that after 2^k-1 seconds the lamps $2,4,6,...,2^k$ will be on and all others off where no lamp bigger than $2^k$ was turned on. Proof: For $k=1$ it is obvious. Suppose it is true for $k=n$ now we prove for $k=n+1$. Firs after $2^n-1$ seconds $2,4,6,....,2^n$ are on and others off. In the next move we have $2^n+1$ is on and others off. We have that by symmetry wrt $L_{2^n+1}$ that lamp is always off(and it starts as turned on) so it behaves as $L_{1}$ did on the start. So we have that lamps $2^n+1,2^n,2^n-1,...,2$ and $2^n+1,2^n+2,....,2^n+2^n$ behave the same way as $1,2,3,...,2^n$ did in the first $2^n-1$ moves. Because of this we have that after using $2^n-1+2^n=2^{n+1}-1$ moves in total lamps $2,4,6,8,....,2^{n+1}$ are all on and others are all off. Back to the problem. If $n=2^s+1$ we have that after $2^s-1$ moves lamps $2,4,6,...,2^s$ are on and in the next move they are all off. If $n=2^s+2$ we have that after $2^s-1$ moves lamps $2,4,6,...,2^s$ are on and in the next move only $2^s+1$ is on and others off(which is symmetric to the situation after second where only $2$ is on) so we will never turn the all off(because the game is periodic because of symmetry and if they were all off at one point they would never turn back on)

A cute problem, I liked it a lot.

Maybe it will sound stupid , but I don't understand the problem, can anybody explain what happens to leftmost or rightmost lamp(with several examples)? For example, what happens to 1,0,0 after one second?(1 is on position, and 0 is off position) it becomes 1,1,0, or 0,1,0 or 0,1,1? Thank you.

Does anyone know if all lamps turn off iff $n=2^k$? I think it's true but I'm unsure.

a) For $n=2$ we can turn it all off. Now note that if for some $n$ we can turn them all off we will turn them off for $2n$. We use induction. Let lamp be $1$ if it is turned on and $0$ otherwise. After some time we will have $n$ ones followed by $n$ zeroes. In next move we have $n-1$ zeroes then $2$ ones and then $n-1$ zeroes again. Now second $n$ lamps act the same as the first $n$ lamps until that moment, and first $n$ lamps act the same by simmetry (from right to left). So $n$-th and $n+1$-th lamps will always be in the same state so they can basically ignore each other. After some number of moves we wil get $2n$ ones and in the next move $2n$ zeroes so all lamps are turned off. Now we have proven that for $n=2^k$ all lamps will be turned off. b) Take $n=3*2^k=2^{k+1}+2^k$. We will have $2^{k+1}$ ones at some moment followed by $2^k$ zeroes. Let this be state $l$. In the next move we will get $2^{k+1}-1$ zeroes then $2$ ones and then again $2^k-1$ zeroes. Now for some time, like in the part a) they will act simmetricaly until the moment when we get $2^k$ ones at the end which means by simmetry that they are followed by $2^k$ more ones which are followed by $2^k$ zeroes(all this from right to left). Note that this state of all the lamps is simmetrical to the state $l$ so it will repeat and the lamps will never be off.

I like it, nice one. And surprisingly I solved this one rather quickly - like 10 min - especially for a combinatorics problem. As for the notation: $L_i \equiv T$ or $L_i \equiv F$ means $L_i$ is on or $L_i$ is off. Furthermore $(\dots) \rightarrow (\dots)$ denotes the change of the states in a second. (a) Choose $n=2^k$. We want to proceed by induction. Base step: Note $(L_1,L_2) \equiv (T,F) \rightarrow (T,T) \rightarrow (F,F)$. Inductive hypotesis: For $(L_1,L_2,\dots,L_{2^k})$ satisfy the following conditions: (i) There is some time, when $L_{2^k} \equiv T$. (ii) The first time, when $L_{2^k} \equiv T$ happens, we also have $(L_1,L_2,\dots,L_{2^k}) \equiv (T,T,\dots,T)$. (iii) The next step is $(L_1,L_2,\dots,L_{2^k}) \equiv (F,F,\dots,F)$. That's also the first time, when that state is achieved. Induction step: Look at $(L_1,L_2,\dots,L_{2^k+2^k})$. Before $L_{2^k} \equiv T$, it'll be an $F$, and so will be $L_{2^k+1},L_{2^k+2},\dots,L_{2^{k+1}}$, as $(L_{2^k},\dots,L_{2^{k+1}})$ stays constant for that period of time. The first time, when $L_{2^k} \equiv T$ happens, we have \[ (L_1,\dots,L_{2^{k+1}}) \equiv (T,T,\dots,T,F,F,\dots,F) \rightarrow (F,F,\dots,F,T,T,F,F,\dots,F) \]with $2 \cdot (2^k-1)$ times state $F$. The tuple above is symmetric about the symmetry axis and thus it'll stay symmetric about that axis. The right side of the symmetry axis contains a $2^k$-tuple $(T,F,F,\dots,F)$. By inductive hypotesis, this will hit $(...,T)$ sometime. And and that time, it'll hit $(T,T,\dots,T)$. So $(L_1,L_2,\dots,L_{2^{k+1}})$ will hit $(T,T,\dots,T)$ for the first time, when $L_{2^{k+1}}$ hits $T$ the first time. The next step is $(F,F,\dots,F)$ and obviously before that, this state has never been achieved due to the inductive hypotesis. Done. $\hfill \square$ (b) Choose $n=2^k+1$. Note \[ (L_1,L_2,\dots,L_{2^k+1}) \equiv (T,F,F,\dots,F) \rightarrow (T,T,F,F,\dots,F) \rightarrow \dots \rightarrow (T,T,\dots,T,F) \rightarrow (F,F,\dots,F,T,T) \]due to the things proven in (a). But that's symmetric to $(T,T,F,F,\dots,F)$. So basically, this one is periodic and due to (a), it'll has never reached $(F,F,\dots,F)$ in between. $\hfill \square$

İt is also true that the number of lamps that are on will always be the power of 2.So taking $n $ not power of 2 $\implies $ b is done.

And also in k th step there will be at most k lamps that this operation has influence on it. So by induction this problem is destroyed.

İt seems right but İ cannot prove that at every step the number of lamps that are on will be the power of 2.Can anyone help me to prove this?

This is basically a problem similar to CANADA 1994.

Yeah it is

Notice that this construction is basically the right side of Pascal's triangle where odd means the light is on (We know everything down the center line is even by symmetry) until the lights "reach" the right side. It's clear that after the nth second, the rightmost light that is turned on is the n+1th light, assuming that n+1 is less than the number of lights. a) Consider $2^k+1$ lights to reach a position where every other light is turned on after $2^k-1$ seconds, since we know that $2^k-1$ is all ones in binary, so by Lucas's theorem, all numbers in this row of Pascal's triangle are odd. Then, on the next second, all lights are clearly turned off. b) Consider $2^k+2$ lights to reach a position where only the second to last light is turned on after $2^k$ seconds. Once again, by Lucas's theorem, we can confirm only one light will be on, which is the $2^k+1$ th one. Then, we can see by symmetry this is identical to the position after 1 second, and at no point in between were all the lights off (since there is no row of Pascal's triangle with all zeroes), so this process will repeat indefinitely with always at least one lamp on.

This one was simple! First of all, let $0$ and $1$ denote the switched off and switched on states of a lamp respectively. From now on, we will denote the lamps with only $0$s and $1$s. (a) We will show that if $n=2^k$ for $k\geq1$, then eventually all lamps will be switched off, that is, all the bits will become $0$. We proceed by induction. For $n=2^1=2$, the process is just $(10)\rightarrow (11)\rightarrow (00)$. Now suppose for some $k\geq 1$, an arrangement of $n=2^k$ bits will eventually become all $0$s in the process. We further assume that the in the second last step of the process, the bits will be all $1$s and that this will be the only time that the last bit became $1$. Now for $n=2^{k+1}$, imagine a partition between the first $2^k$ and the last $2^k$ bits. We can see that till the $2^k$th bit does not become $1$, the bits to the right of the $2^k$th bit will remain $0$. Now for the first $2^k$ bits, we use the induction hypothesis, and consider the step where all of the first $2^k$ bits become $1$. The next step results in $(111\dots111|000\dots000)\rightarrow (000\dots 001|100\dots000)$ where $|$ represents the partition. Now note that the arrangement has become symmetric and for the rest of the process, it will remain so, since the process when started from the leftmost bit, is a reflection of the process when started from the rightmost bit. Also since the $2^k$th and the $2^{k+1}$th bits will always be identical, so their modification will only depend on the neighboring bit to their other side of the partition. So we can separately consider the process on the two sides of the partition, since the "one-neighbor condition" for the $2^{k}$th and $2^{k+1}$th bits will be fulfilled. Then each side of the partition will look exactly as if we started with two sets of $2^k$ bits with the given problem condition. By our hypothesis, we know that the process would eventually lead to all $0$s, and the hypothesis also ensures that only in the step before all the bits become $0$, will the last bit be $1$. Hence we are done. $\blacksquare$ (b) We shall show that for $n=2^k+1$ where $k\geq 1$, the lamps will never be all switched off, that is, the bits will never be all $0$s. Consider an arrangement of the $2^k+1$ bits. We note that the last bit will remain $0$ until the $2^k$th bit becomes $1$. By part (a), we know that this occurs for the first time when the first $2^k$ bits are all $1$s. Then in the next step we get $(111\dots1110)\rightarrow (000\dots0011)$. This arrangement is exactly the reflection of the arrangement after the first step, that is $(100\dots000)\rightarrow(110\dots000)$. Since the process works exactly similarly on reflections, so we know that the arrangement of bits will keep repeating and so we will never reach all $0$s. $\blacksquare$

I claim that for all positive integers $k$, taking $n=2^k$ works, and on the $n-1$th move, all the lamps will be on. Clearly this holds for $n=2$, so now we induct on $k$. Consider the case $n=2^{k+1}$. On the $2^k-1$th move, the first $2^k$ lamps will be on, by the inductive hypothesis (we don't need to worry about the tail having only one neighbour, since it's easy to show that the $i$th lamp first turns on during the $i-1$th move). Then on the $2^k$th move only the middle two lamps will be on. Then we can split the lamps in half and again by the inductive hypothesis it takes another $2^k-1$ moves for all lamps to be on. Then take $n=2^k+1$. Clearly after $2^k$ moves, the last two lamps will be on. Then by symmetry the lamps will never be all off (this is equivalent to the problem after just one move). We are done. $\blacksquare$

I claim that for all $n=2^k$ where $k\in \mathbb{Z}^+$, until all lamps turn on, the last lamp will never be on, and that after all lamps turn on, then all lamps will turn off, proving that there are infinitely many integers $n$ satisfying part $(a)$. We will use induction. For simplicity, let $0$ represent an off lamp and $1$ represent an on lamp. Then, for $n=2^1$, the lamps go $10$ then $11$ then $00$, which satisfies our claim. Assume that for some $2^k$, our claim is satisfied. We will now prove that our claim is satisfied for $2^{k+1}$. We claim that there will eventually be a point when the first $2^k$ lamps are on and the last $2^k$ lamps are off. This is because the $2^k$th lamp is never on until the first $2^k$ lamps are on, so the $2^k+1$ lamp will always be next to $2$ off lamps, so it will stay off until after first $2^k$ lamps are on. $1$ second after this point, there will be $2^k-1$ off lamps followed by $2$ on lamps followed by $2^k-1$ off lamps. Because of symmetry, this is the same as having $2$ groups of the $2^k$ case. The last lamp will never be on until all lamps turn on because it is true for the $2^k$ case. This completes our induction. This proves part $(a)$. I claim that for all $n=2^k+1$ where $k\in \mathbb{Z}^+$ and $k\ge 69420$, the lamps will never be all off, proving part $(b)$. After the first second, we will have $2$ on lamps followed by $2^k-1$ off lamps. At some later point, we will have $2^k$ on lamps followed by $1$ off lamp. This is because, by the claim in part $(a)$, the $2^k$th lamp will never be on until the first $2^k$ lamps are on, so $2^k+1$ will also be off until after the first $2^k$ lamps turn on. $1$ second after this point, we will have $2^k-1$ off lamps followed by $2$ on lamps. This is simply what we got after the first second, but in reverse order. Therefore, by symmetry, at some later point, we will have $2$ on lamps followed by $2^k-1$ off lamps, finishing our loop so we can never have all $2^k+1$ lamps be off. This proves part $(b)$.

The first thing that happens will be $L_1$ and $L_2$ being switched on and all others being switched off. We will call this the starting state for convenience. We first prove a lemma that will be used for both parts. Lemma. For all positive integers $k$, there will eventually be a state such that the first $2^k$ lamps are on and all the rest are off, given that we are starting from the starting state and there are at least $2^k$ lamps. Also, if $k>1$, this happens after the event for $k-1$ happens, and from the second after the $k-1$ event, $L_1$ and $L_{2^k}$ are first on when this event for $k$ occurs. Proof. We proceed by strong induction. Base case $k=1$ is trivial. Therefore, for the inductive step, assume that this is true for $1,2,\dots,k$. Then, we use the statement for $k$ and start from that state. The next thing that happens is that $L_{2^k}$ and $L_{2^k+1}$ are on, and all other lamps are off. Now, consider lamps $L_{2^{k-1}+1}$ to $L_{3\cdot2^{k-1}}$. This is precisely the position that happens one second after the $k-1$ case, and therefore the $k$ case happens again, meaning that there will eventually be a move such that all lamps in that range are on and all other ones are off. The next second, only lamps $L_{2^{k-1}}$, $L_{2^{k-1}+1}$, $L_{3\cdot2^{k-1}}$, and $L_{3\cdot2^{k-1}+1}$ are on. This is again precisely the second after the $k-1$ case, but repeated twice for lamps $L_1$ to $L_{2^k}$ and lamps $L_{2^k+1}$ to $L_{2^{k+1}}$. Therefore, eventually, all of those lamps are on. These two groups don't interact with each other because of our first on condition, and the first on condition clearly holds true here. (a) Let $n=2^k$ for positive integers $k$. The second after the event for $k$ occurs, everything is off and clearly will stay off forever. (b) Let $n=2^k+1$ for positive integers $k$. After the event for $k$ occurs, the next second, $L_{2^k}$ and $L_{2^k+1}$ are the only two lamps that are on. This is now the starting position but flipped, so by symmetry this clearly lasts forever.

a) $n=2^k$ works. We induct, with the base case being obvious. By the inductive hypothesis, the first $2^k$ turn on. Then only the middle 2 are on. We can think of this as two groups of $2^k$ going together, so the lamps will all turn on. b) $n=2^k+1$ doesn't work. By part a), the first $2^k$ turn on, and then after, only the last two will be on. This repeats infinitely, and we are done.

Great, interesting problem! This problem suggests stuff like induction, and powers of 2 since it's easy to split them. Indeed, for part a) 2^k suffices and b) has 2^k+1. The key is to see that by induction (base case k=1 trivial) time=2^k seconds (from henceforth call it $T_i$) at $T_{2^{k-1}}$ all 2^{k-1} left lamps are on and the right ones are off. First note that since lamps only can light up consecutively (as in if there are some consecutive lamps L_i,L_{i+1},...,L_{i+j} are off with L_{i-1} on, L_{i+1} cannot be lit until L_i is, and this spirals to the start meaning that no lamp can turn on until their partner to the left turns on, which each move taking one second) means that L_{2^k} cannot light up until at least T_{2^k}. Inductive step: at T_{2^{k-1}} the left half is lit up and the right half is off. Then T_{2^{k-1}+1} --> middle two are on. Now it's the same as inductive hypothesis occuring twice at the same time in both halves, meaning L_{2^{k-1}} and L_{2^{k-1}+1} will turn off and on at the same time (due to turning off will still turn off since they're the same state, and turning on will still turn on (since to turn on in the T_{2^{k-1}} subsection there would need to be a lamp of opposite state anyway). This means that all lamps are on at T_{2^k} (since T_{2^{k-1}+1} is considered as T_1 in either state). $\square$ Now, for part a, since T_{2^k} all lamps are on, the next second they're all off. As for part b, since T_{2^k} all are on, T_{2^k+1} means only the right two most lamps are on. This is just the mirror image of T_2 when only the leftmost two lamps are on, meaning it will repeat into all left 2^k lamps with (by reflection) being on with 2^k+1th lamp being off, and infinitely repeat into that same situation again. $\blacksquare$

Claim: When $n$ is a power of $2$, the lamps will eventually all turn on (which also implies that they will all turn off). Proof: Base case $n = 2$ is obvious. For the inductive step when $n = 2^{k+1}$, note that the the first $2^k$ lamps will be on. Then the lamps in the $2^k$ and $2^k+1$ position will be the only ones on after the next step. At this point the future arrangements will always be symmetric and thus the lamps at positions $2^k$ and $2^k+1$ are solely determined by one neighbor. Thus, the two halves $1\dots 2^k$ and $2^k+1\dots 2^{k+1}$ behave just like when $n = 2^k$, and so all lamps will be on at some point. $\square$ Claim: When $n = 2^k+1$ for $k \geq 1$, the process will continue forever. Proof: From our first claim then we know the first $n-1$ lamps will be on. But then we must end up with the last two lamps being on in the next step. This state is equivalent to the second state of any process, where the first two lamps are on. Thus, the process cycles, and will never end. $\square$ This proves the problem. $\blacksquare$

a. Claim: If $n=2^k, k>=1$, then the lamps will eventually all turn off. Proof: We will prove this in 2 parts. The first part is that the the lamps will reach the state $1...2^k-1$ will be off, lamps $2^k, 2^k+1$ will be on, and lamps $2^k+2, 2^{k+1}$ will be off, and the second part is that the lamps will eventually all turn on (which means that they will all turn off) from the state mentioned above. We will prove both parts by induction. Base case: $n=2$, which goes $10, 11, 00$. Inductive step for the first part: We see that when we get to the state $111...10...000$ where there are $2^k$ $1$s and $2^k$ $0$s, we will get to this state. Also, as we get that the first $2^k$ (as our base case) are on (and will be on for the first time, as a result of the induction), this is achievable, and therefore the first part is proven. Inductive step for the second part: Once we reach the state $0...11...0$, then we can split the string up into 2 $10...0$s of size $2^k$ each, proving it for $2^{k+1}$ Therefore $a$ is true. b. Claim: If $n=2^k+1$, then it repeats forever. Proof: By $a$, we know that $2^k$ will eventually be all on. Therefore, it will be in the state $1111.....110$ ($2^k$ $1$s), and then go to $00000...01$, which is just a reflection of the starting state, and therefore it cycles. Therefore $b$ is true

Nice problem but I cannot prove this two statements : 1. The number of on lights at any second after 2 seconds is even . 2. All the lights are eventually off iff $n$ is some power of $2$. actually if $1$ is true we can easily discard the odds and i guess without using $1$ we can prove the $2$ nd one by inducting on $\lfloor log_2 n \rfloor$.I mean , let $2^k\leq n< 2^{k+1}$ then after some stage we will get the scenario $\underbrace {00..01}_{2^{k-1}}||\underbrace{10...0}_{n-2^{k-1}}$ . But then we have to prove that those two middle positions have always same state (then the left part will not be affected by the right part sort of ) Could anybody help ?

For (a), I claim that $n=2^m$ works. We proceed by using induction. Clearly the base case with $m=1$ works. We show that $n=2^{m+1}$ also works. We also show in our induction that is takes exactly $2^m$ steps for the case $n=2^m$ for all entries to be $=0$. Now for $n=2^{m+1}$, we get that after $2^m - 1$ moves, the first $2^m$ entries are all $1$. And after another move, we get that all entries except the $2^m$ and $2^{m} + 1$th ones are $0$. Now note that due to symmetry, the action of the next $2^m$ moves on the first $2^m$ entries and the action on the latter $2^m$ entries work like they are independent from each other which finish by using our induction hypothesis. For (b), I claim that $n = 2^m + 1$ works. After hte first move, we have $100\ldots0$. From part (a), after $2^m-1$ moves, we have all the first $2^m$ entries are $=1$. Then after another move, we have the following configuration, $00\ldots 0011$ which is just the reverse of what we had after move $1$, and so, due to symmetry, we never reach a position where all the entries are $0$ and keep on alternating between the configurations we showed above and this goes on forever.

For brevity, we describe a current state of $n$ lamps as a $n$-element binary tuple with $0$ indicating an off lamp and $1$ otherwise. (a) Instead of showing that all lamps will eventually be off, it is sufficient to show that eventually, all lamps will be on. We claim that $n = 2^k$ works for positive integers $k$. Clearly $k = 1$ works as we get $(1, 0) \to (1, 1)$, observe that the rightmost lamp never turns on until the last state. Now assume that $n = 2^k$ for some positive integer $k$ works, and that the rightmost lamp will only turn on until the last state. For $n = 2^{k + 1}$, by our previous assumption, the first $2^k$ lamps will eventually turn all on, as before the state the lamp in the $2^k$ spot will never turn on, and thus will not interact with any lamps past $2^k$. The next second, we achieve the state $(0, 0, \dots, 1, 1, \dots, 0, 0)$ where lamps $2^k$ and $2^{k + 1}$ are on. Each side (Lamps from $1$ to $2^k$, and lamps from $2^k + 1$ to $2^{k + 1}$) "mirrors" each other, and eventually each side will turn all on respectively, making all the lamps on. An important detail to notice is that the rightmost lamp only turns on in the final state, so that the induction can work. Our proof is complete. (b) We claim that $n = 2^k + 1$ works for positive integers $k$, and all lamps will never turn off. By our last claim in (a), the first $2^k$ spots will eventually turn all on, at $(1, 1, 1, \dots, 1, 0)$. The next second, only the last two lamps are on, giving the state $(0, 0, 0, \dots, 1, 1)$. However, this is simply the reverse of the state achieved on the second state, hence we reached a loop where we never reach a state of all lamps being off. Our proof is complete.

(a) For all n which are powers of 2, all the lamps will eventually become on, and they go off immediately after. n=2 is 10 11 n=4 is 1000 1100 0110 1111 n=8 is 10000000 11000000 01100000 11110000 00011000 00111100 01100110 11111111 We will use induction to prove it true for n=2^(k+1). The top left box is the sequence for 2^k. The top right box is 2^k rows of 2^k zeroes. The bottom left box is the sequence for 2^k, but each row is reversed. The bottom right box is the sequence for 2^k. (b) For all n=2^k+1, we eventually get 1...10 (2^k 1s followed by a 0), and since this is the reverse of the not of 10...0 (1 followed by 2^k 0s), the sequence clearly repeats forever and we never get 2^k+1 0s. To see this, just add a 0 at the end of every row of the n=2^k construction from (a). This works because the only time the last lamp is on is at the end of the n=2^k construction from (a).

bad formatting because copied from my solution on mathdash. use the obvious binary interpretation. a) i claim that 2^n works for all n >= 1. we use induction, with the strengthened claim that the rightmost lamp is never turned on until all of them are. base case is trivial, for inductive step consider we have 2^k proved, wanna prove 2^{k + 1}, then at some point we're gonna have 2^k 1s followed by 2^k 0s (no bits after the first half could have been affected, since by the strengthened hypothesis we didnt touch the rightmost one in the first half yet), the next operation will result in having 2^k - 1 0s, followed by 1, and then the mirror of that. its easy to see the next sequence of moves will result in two symmetrical processes, each starting with one lightbulb turned on in the corner and then going from there. now we just have to show each process is identical to the one where we have just 2^k lightbulbs, which is just equivalent to saying the left center and right center light bulbs behave identical to corner lightbulbs, which is true since they border an identical lightbulb. the part about not turning on the rightmost until the end is also true, since both the left and right processes terminate at the same time and the rightmost bulb is just the rightmost bulb of the smaller right half process. b) i claim that 2^n + 1 works. by the claim from part a), we eventually end up with 2^n 1s followed by 0, after operating on that we then get 2^(k - 1) 0s followed by 2 1s, which is equivalent to the mirror of the result after the first move, so by symmetry we have periodicity.

Wow. Denote $0$ as an off light and $1$ as an on light. From now on, we call a light a "term". (a) We claim that numbers of the form $2^k$ do the trick. In fact, we will show an even stronger statement: that for $2^k$, the process is like $$100\dots0 \to 11\dots10\dots00 \to 00\dots0110\dots00 \to 000\dots000,$$where in the third state there are $2^{k-1} - 1$ zeroes on either side, and in the second state there are an equal number of $0$s and $1$s. The proof is by induction on $n,$ with the base case $k=1$ being immediate. For the inductive step, assume that this holds for $k,$ and we wish to show it holds for $k+1.$ We start off as $$100\dots0,$$and by the inductive hypothesis, this turns into $$11\dots10\dots00.$$Now we consider what happens to this. The leftmost $2^k-1$ terms all become $0,$ as do the rightmost $2^k-1$ terms, but the middle two terms both become $1.$ Thus we end up with $$00\dots0110\dots00.$$Then operating on the middle $2^k$ terms, by the inductive hypothesis this becomes $$00\dots 011\dots110\dots00,$$where there are $2^k$ ones in the middle. Applying a move to this gives us $$00\dots 0110\dots0000\dots0110\dots00,$$where the numbers of zeroes in each section are $2^{k-1} - 1, 2^k - 2, 2^{k-1} - 1,$ respectively. Then applying the inductive hypothesis on the first half of terms gives $$11\dots1,$$and same for the rightmost terms. Thus we end up with our entire string being $11\dots1,$ which turns into $00\dots0,$ and the induction is complete. Thus all powers of $2$ work. (b) This time, we claim that numbers of the form $2^k + 1$ do the trick. We start off as $100\dots0$, and this becomes $1100\dots0.$ Now, by part (a), at some point, all but the rightmost light become $1.$ Thus we have $111\dots10.$ This becomes $00\dots011.$ At this point, we have $1100\dots0$ reversed. Additionally, if we got to $00\dots0$ at some point, we get stuck in the loop $00\dots0, 11\dots1.$ We never end up in this loop, so when we go from $1100\dots0$ to $00\dots011,$ we do not hit $00\dots0.$ Hence we get stuck in a cycle, and the lights are never all off.

Fun. a) I claim that powers of two work ($2^k$). I show this by induction. The base case $k=1$ is obvious. As the inductive step we assume that the result is true for $k=m$. We now consider $k=m+1$. $$\underbrace{11...11}_{2^m}\underbrace{00...00}_{2^m}$$Notice that because of our inductive hypothesis, in the algorithm for $n=2^{m+1}$ the above scenerio occurs. Then, after one second we immediately obtain the state $$\underbrace{00...00}_{2^m-1}11\underbrace{00...00}_{2^m-1}$$Now, consider the first $2^m$ and last $2^m$ digits here. Notice that the two blocks are mirror reflections of each other across a central vertical axis, and they will continue to be so by obvious symmetry. Now just considering the last $2^m$ digits, notice that they will all eventually become $\underbrace{11...111}_{2^m}$ by our inductive hypothesis, and therefore so will the first $2^m$ and we are done (once it reaches all $1$ it will proceed to reach all $0$). Also notice that the two halves will never "interfere" with each other and provide an outside source thus violating our inductive hypothesis. This is because the central two digits are always the same, so the other one of them will never matter to the other. b) I claim that $2^k+1$ works. Using a), notice that it will eventually come to $$\underbrace{111...111}_{2^k}0$$. After this operation it will become $$\underbrace{00...000}_{2^k-1}11$$. Now consider reflecting this to come to $$11\underbrace{00...00}_{2^k-1}$$Now, just considering the first $2^k$ digits it is clear that they will all become $1$ using part a). Therefore we come to $$\underbrace{11...111}_{2^k}0$$. Thus is just our initial case a few steps back so it will keep cycling and never reach all $0$. We are done.

a) We will show by induction that for $n=2^m$ the lights will eventually all be on. The base case, when $m=1,$ is trivial. Now, suppose that our proposition holds for $m=k$ for some positive integer $k.$ Then for $m=k+1$ by our inductive hypothesis eventually the first $2^k$ lights out of the $2^{k+1}$ lights will be on. A second later, the middle two lights will be on, while everything else is off. Note that from here, the pattern of lights will clearly always be symmetrical, therefore, the first and last $2^k$ lights will act as if they are separated, because the lights where they are connected (the middle two) will always be the same, thus whatever happens to them will completely depend on their other neighbor (not in the middle two). Therefore, by the inductive hypothesis both groups of lights will eventually have all their lights turned on. Hence, are induction is finished, and it follows that for $n=2^m$ the lights will then become off. QED b) Note that for $n=2^m+1$ by above eventually the first $2^m$ lights will turn on. (Clearly all lights being off will never happen as otherwise the lights will stay that way) A second later, only the rightmost light will be on, which is essentially the same situation we had initially. Therefore, the lamps will never be all off in this situation. QED