Toggling lights 3 at a time

Alice and Bob are playing a game. $n$ lights are put on a line with individual switches, initially all off. Then the two phases happen as follow:

1. Alice turns on some of these lights

2. Bob may do these actions: choose a contiguous block of 3 lights and toggle these 3 lights. He may repeat these actions as many times as he wants for different blocks.

And the scoring of the game is as follows:

In phase 1, Alice gets a -1 point for each light that she turns on. In phase 2, Alice gets a +1 point every time Bob performs an operation. Then at the end of the game, Alice gets $i$ points if light $i$ is on. Obviously Alice wants her score to be as high as possible, and Bob wants her score to be as low as possible. Determine the maximum points that Alice can get if both players are playing optimally.

Solution

Let $T_k$ denote the action by Bob of toggling a contiguous block of $k, k+1, k+2$, where $k \in [1, 98]$. If light $k+3$ is on and light $k$ is off, by performing $T_k + T_{k+1}$ he can turn off $k+3$ and turn on $k$. The net effect to the score is -1 so this move is beneficial to Bob. Therefore, he would keep doing it as long as there are lights on at $k > 3$. Furthermore, if there are 2 lights on $k > l$ such that $k \equiv l \mod 3$ then by repeating the operation above Bob can turn off both lights. The net effect to the score is $-k-l+2\frac{k-l}{3} < 0$. This means that it is not optimal for Alice to turn on two lights that have the same residue mod 3. So at most Alice should turn on 3 lights. But even then, if we ever arrive at the condition where lights $(1,2,3)$ are on, then Bob can perform $T_1$ to turn off all the lights. So Alice should turn on at most 2 lights.

The final condition that is most beneficial to Alice is either $(3)$ or $(1,2)$, both having the same value, and both are accessible from each other in phase 2. But obviously it's more beneficial for Alice to turn on only 1 light, and it should be the largest light divisible by 3, so that Bob has to spend a lot of moves moving it to the smaller number. So Alice should turn on $3\lfloor n/3 \rfloor$, and Bob will have to move it all the way to 3.

The total score is then $-1 + 2\lfloor n/3 \rfloor + 3 = 2\lfloor n/3 \rfloor +1$

Note: the number 3 can be replaced by a larger number $p$ but the principle is the same. Any light on above $p$ can be shifted down for a net gain for Bob. However, the final condition is tricky. Take $p=5$ for example. We don't want $(1,2,3,4,5)$ because then Bob can simply turn them all off in one fell swoop. We also don't want $(3,4,5)$ because Bob can still replace it by $(1,2)$ for a net gain. In fact, the optimal condition for Alice is $(3,5)$ because while Bob can replace it by $(1,2,4)$, it costs him 1 point to do so, so it's not a beneficial move for Bob. Likewise, for $p=6$, the best condition for Alice is $(5,6)$ because it's "just under" $(1+2+3+4+5+6)/2$. The number of lights that would be left on so that the sum is just under $n(n+1)/2$ is $\lfloor (n-1)/2 \rfloor$ which can be proved by induction. However, the exact configuration is harder to determine in closed form expression. This matters because in the course of shifting the lights down during phase 2, Bob may inadvertently have to perform the same $T_k$ twice in which case he would just not perform that action, so the calculation of final point count becomes more complicated.