Subtask 1

If ~M = 2~, then Josh should go second, using the strategy described in Sample Interaction ~2~.

Otherwise, ~M \ge 3~. We can show that Josh can force a win if he goes first, according to the following strategy:

• First, toggle any cell. After Nils responds, there will be two black cells.
• Then, repeatedly until Josh wins, check if there are two adjacent black cells. If so, toggle an adjacent cell to form a line of three. Otherwise, pick any cell between the two closest black cells, and toggle it black.

Let ~D~ be the minimum distance between any two black cells. Because Nils can't undo Josh's last move, it is easy to show that ~D~ decreases after each pair of turns. Once ~D = 1~, Josh can immediately force a win. This proves that this strategy is correct.

Implemented naively, this solution will only score ~60\%~ of the points, because it can take up to ~N - 1~ pairs of turns for ~D~ to reach ~1~. However, if we always toggle the cell in the middle of the two closest black cells, ~D~ is reduced to at most ~\lceil \frac{D}{2} \rceil~ after each pair of turns. This is sufficient for ~100\%~ of the points.

Subtask 2

Let's consider ~N > 2~. It's fairly easy to adapt our subtask ~1~ solution to work in two dimensions:

• First, toggle any cell. After Nils responds, there will be two black cells.
• If these two cells are in different rows and columns, toggle any cell which shares a row or column with both cells. After Nils responds, there will be at least two black cells in the same row or column.
• Then, repeatedly until Josh wins, check if there are two adjacent black cells. If so, toggle an adjacent cell to form a line of three. Otherwise, pick any cell between the two closest black cells in the same row or column, and toggle it black.

Here, we instead define ~D~ as the minimum distance between any two black cells in the same row or column. The correctness of this strategy is very similar to the proof in subtask ~1~.

Note that for full points, the first cell toggled should be in the middle of the grid, to minimize the starting value of ~D~.

The final case is where ~N = 2~. It can be shown that Josh can win if he chooses to go second, since it is always possible to force the invariant that after Josh's turn, there should be exactly one black cell in each row.