, 2015

a. Let's look at what happens with the state of one light when executing a move. Each move either changes or preserves the state of the light. Thus the final state of some light only depends on the number of moves made that change the state of that light, and not on the order of the moves made. Therefore the final state of all the lights also does not depend on the order of the moves made.

b. This is possible for exactly those $n$ which are divisible by 3.
Suppose first that $n$ is divisible by 3 and let's prove that in this case we can indeed reach the desired state. Let $P_i$ be the move where we change the states of the $i$-th, $(i+1)$-st, and $(i+2)$-nd light in the line. Since $n$ is divisible by 3 and each move changes the state of 3 lights we can change the states of all the lights in the row by making $\frac{n}{3}$ moves $P_1, P_4, P_7, \dots, P_{n-2}$, and thus reach the desired state.

Now let's prove that we can reach the desired state only if $n$ is divisible by 3. We already know that the order of the moves is not important, so we may assume that we make moves $P_i$ in the increasing order determined by $i$. If we make the move $P_i$ twice the state of the light is preserved. Therefore we may also assume that we make each move $P_i$ at most one time. This basically means that we only need to decide for each move $P_i$ if we make it or not. At the end each odd light must be turned off and each even light turned on. Since we need to change the state of the 1st light, which can only be done by the move $P_1$, we must make the move $P_1$. After this move the first three lights are already in the desired state. Since $P_2$ is the only other move that changes the state of the 2nd light we must not make this move. Among the moves $P_3, P_4, P_5, \dots$ the move $P_3$ is the only one that changes the state of the $3\text{rd}$ light, thus we must also not make this move. Now we are at the move $P_4$ and we make a similar argument. We need to change the state of the $4\text{th}$ light, hence we must make the move $P_4$. After this move the $4\text{th}$, $5\text{th}$, and $6\text{th}$ light are in the desired state, so we must not make the move $P_5$ nor the move $P_6$. We continue in a similar matter, we make move $P_7$ and don't make moves $P_8$ and $P_9$, and so on. This means that we must necessarily make the sequence of moves $P_1, P_4, P_7, \dots$. For this sequence to change the state of all the lights in the line, $n$ must be divisible by 3. Indeed, if $n$ has remainder 1 when divided by 3, then we will not change the state of the last light since the move $P_n$ is not allowed as it only changes the state of one light. Similarly, if $n$ has remainder 2 when divided by 3, then we will not change the state of the last two lights since the moves $P_{n-1}$ and $P_n$ are not allowed.