Alice has a winning strategy for all odd $n$. It has already been observed that Alice cannot lose when $n=1,3,5$, and the following construction will work provided $n\ge 5$ is odd. (For even $n$, the game is a draw as observed by Mohemnist and JDH.)

The first stage is the same as dhy's construction: Alice will attempt to get a line of length $k\ge 3$. Alice starts by playing anywhere, and we suppose that Bob plays so that there are $n$ spaces to the left and $m\ge n$ spaces to the right of Alice's play.

- If $n\ge 2$, i.e. $b\_\dots\_a\_$, then Alice plays to the left yielding $\_aa\_$, so now Bob cannot prevent a run of length 3.
- If $n=1$, i.e. $b\_a\_$, then Alice plays to the right, $b\_aa\_$, and again Bob cannot prevent a run of length 3.
- If $n=0$, then Alice plays $ba\_a\_$. If Bob is to prevent a run of length 3 he must play $baba\_$, whereupon Alice plays $baba\_a\_$ and again Bob's move is forced. Eventually we reach the end of the necklace, for example with size 7 we reach the state $bababa\_$ and Alice can now win with the only remaining move.

Once obtaining at least 3 points in a row, she continues to extend the sequence with each move until both ends are blocked. At this point we have the configuration $b(ab)^ja^kb$, and of the $n-2j-k-2$ remaining spaces exactly $k-2$ of them have $b$'s. Alice will now attempt to prevent Bob from getting $k$ in a row to win.

We can reduce to the case $k=3$ by removing $k-3$ of Bob's non-endpoint plays (i.e. removing the point entirely); any sequence of length $3$ in the reduced game will be extended to $k$ at worst.

Let a "segment" denote a maximal run of points containing none of Alice's points. Initially, there will be one free segment of even length $m=n-2j-k-2$ (plus $j$ additional filled segments of length 1).

Note that the situation $b\_^ib\_^jb$ where $i$ and $j$ are both odd is a win for Bob, because Alice can block at most one of the spaces, say the right one, and then Bob can either win if $i=1$, or reduce to the smaller situation $b\_b\_^{i-2}b$ where $1$ and $i-2$ are again both odd. This cannot be the initial setup because this requires $m=i+j+3$ to be odd, but Alice must take care to prevent it arising in further play.

During the course of the game, Alice's plays will split up the free segments and reduce their length. We maintain the following invariant:

Each segment is either "active" or "passive". Every segment is passive after Alice's move, and at most one segment is active before Alice's move. There is at most one interior $b$ point in the active segment.

- A segment of odd length is passive if it has $<2$ covered endpoints and no interior point.
- A segment of even length is passive if it has $\le 2$ covered endpoints and no interior point.
- A segment of odd length is active if it has $2$ covered endpoints, or it has $<2$ covered endpoints and an interior point.
- A segment of even length is active if it has an interior point.

Initially, there is one (active) segment, of even length, with two covered endpoints and one interior point, plus zero or more passive segments of length 1.

Note that on Bob's move, he can make at most one segment active by playing in it, either by covering another endpoint or adding an interior point. Alice moves as follows:

- If all segments are passive, Alice moves anywhere. This does not affect the passivity of the segments, since it can't create new interior points, and it can't create any segment with two covered endpoints either.
- If the active segment has odd length and no interior point, say $ab\_^iba$ where $i$ is odd, then Alice plays $aba\_^{i-1}b$, producing two passive segments.
- If there is an interior point in the active segment, say $a\underline{b}\_^ib\_^j\underline{b}a$ where the $\underline{b}$ may be $b$ or blank.
- If $i$ is odd and $j$ is even (mirror for the other case), we play $a\underline{b}\_^{i-1}ab\_^j\underline{b}a$, producing an odd length passive segment with one endpoint on the left, and an even length passive segment with $\le 2$ endpoints on the right.
- If both $i$ and $j$ are odd, then the segment has odd length, so one of the endpoints is not present, say $a\underline{b}\_^ib\_^{j+1}a$. In this case we play $a\underline{b}\_^{i-1}ab\_^{j+1}a$ producing two odd length passive segments with at most one endpoint each.
- If both $i$ and $j$ are even, then the segment has odd length, so one of the endpoints is not present, say $a\underline{b}\_^ib\_^{j+1}a$. In this case we play $a\underline{b}\_^iba\_^ja$ producing two even length passive segments with at most two endpoints on the left and no points on the right.

Since these plays preserve the inductive hypothesis, we continue until play ends, after Alice's turn. This means every segment is passive, but a passive segment with no free space is length 1 (if odd length) and length 2 (if even length) by definition, so Bob failed to make a three in a row and Alice wins.

4more comments