A tube week

There were no contests that I'd like to mention during the Jun 22 - Jun 28 week, so let's come back to the Codeforces problem from the previous summary: there are n lamps arranged in a circle (n<=1000), and two players are turning them on and off. Initially all lamps are off. The first player starts by turning on any subset of lamps that are off. Let the number of lamps turned on by the first player be k. Then the second player chooses any subset of k consecutive lamps (along the circle), and turns off all lamps in that subset that were on. Then the first player can turn on any subset of lamps that are off again, and so on. The first player can choose to finish the game instead of making their turn. The goal of the first player is to maximize the number of lamps that are on when the game is finished (and they have to finish the game at some point, they can't continue forever), and the second player tries to minimize that number. What is the optimal strategy for the first player?

Let's call a move of the first player followed by a move of the second player one step. Since the second player always turns off at most the same number of lamps that the first player has just turned on, the number of lamps never decreases after a step. We can further classify the steps into two types: the ones that increase the number of lamps that are on, and the ones that keep it unchanged.

Consider a game that was played optimally by both players, and let's focus on the last increasing step of that game. Suppose the first player has turned k lamps on during their move. If there were k consecutive lamps that were on after that, the second player could have turned them all off, and make the step not increasing. Therefore in order to make an increasing step, the first player needs to keep at least one lamp off among each k consecutive lamps. Therefore the maximum number of lamps that are on after his move is n-ceil(n/k), and then the second player will turn k-1 lamps off in the worst case, so the number of lamps that will be on after this step will be n-ceil(n/k)-k+1.

The first player can pick the value of k that maximizes n-ceil(n/k)-k+1 and achieve such score in the following way: choose any set of lamps of size n-ceil(n/k) that does not have k consecutive lamps, and keep turning on any k lamps from this set that are off. This will guarantee that each step will be increasing until we reach the score of n-ceil(n/k)-k+1.

The second player can guarantee that the score never exceeds max(n-ceil(n/k)-k+1) by simply turning off the maximum number of lamps that they can at each turn, which will make sure that whenever a step is increasing and the first player turned on k lamps, the score after this step will not exceed n-ceil(n/k)-k+1. This is not an entirely formal proof, but the remaining details are left to the reader :)

Thanks for reading, and check back for more!