Alice and Bob playing on a circle

Question

I want to solve this problem:

Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move:

• Alice takes one point that has not been colored before and colors it red.

• Bob takes one point that has not been colored before and colors it blue.

When all $n$ points have been colored:

• Alice finds the maximum number of consecutive red points on the circle and call this $R$.

• Bob finds the maximum number of consecutive blue points on the circle and call this $B$.

If $R \gt B$, Alice wins. If $B \gt R$, Bob wins. If $R = B$, no one wins. Does Alice have a winning strategy for odd $n$?

We still seem not to know for which odd $n$ Alice has a winning strategy. She does for $n=3$, and it seems also for $n=5$. But in general, I'm not sure. Could someone help?

Answer 1

For even $n$, I claim that nobody has a winning strategy, and therefore both players have drawing strategies.

To see this, observe first that by the fundamental theorem of finite games, we know that either one of the players has a winning strategy, or both players have drawing strategies.

Next, I claim that Bob has a drawing strategy, which is simply to use the copying idea of user Mohemnist in the comments. He should simply pair up opposite vertices and make the coloring anti-symmetric. In this way, any string of red vertices is matched by a symmetric string of blue vertices, and therefore Bob can ensure that he will not lose.

But now, it follows that Bob cannot have a winning strategy, since Alice can pretend to be Bob by a strategy-stealing argument. Basically, this amounts to the observation that it cannot be advantageous to go second. That is, Alice can simply start by coloring any vertex red, and thereafter pretend to be the second player, following the winning strategy for Bob, but with swapped colors. If that strategy should ever direct her to color the already-colored vertex, then she can simply take another free move.

So we've shown that Bob has a drawing strategy and cannot have a winning strategy. It follows that Alice cannot have a winning strategy, and so we must be in the case of the fundamental theorem where both players have drawing strategies.

The strategy-stealing argument works regardless of whether $n$ is even or odd, showing that Bob can never have a winning strategy. But of course, we already knew this in the odd case, since Mohemnist showed in that case that Alice has a drawing strategy.

Answer 2

Here is an argument that Alice wins for odd $n$. Label the points $1$ to $n.$

Lemma: If at any point Alice has marked $k$ points in a row and no other points, Bob has marked the two points immediately to the side of those $k$ points, and $k\geq 3$, then Alice has a winning strategy.

Admitting this lemma, Alice can win the original game by playing as follows: First, she marks ball $2$. If Bob doesn't mark a point next to her, then she keeps making marks adjacent to her previous moves until Bob blocks her on both sides, in which case we are now in the situtation of the above Lemma (with $k\geq 3.$) On the other hand, if Bob's second move is say, ball $1$, then Alice marks ball $4$. If Bob doesn't respond by marking $3$, then Alice moves at $3$ and repeats the above strategy to end up in the situation of the Lemma. Else, if Bob marks point $3$, then balls $2$ and $3$ essentially do nothing and we end up in the situation of a game of $n-2$ points where Bob's second move is adjaent to Alice's, which is a win by induction.

Proof of Lemma: We are essentially in the situation of a game with $n-k$ balls in a line, where the two endpoints are blue and Bob has marked $k-2$ other balls blue. Alice's goal here is to stop Bob from getting $k$ blue balls in a row.

To capture this situation, we will define a $(m,k)$-line game to be a game with $m$ balls in a row, some of which start of blue, and Alice (who moves first) and Bob alternating red and blue markings. Alice wins in a $(m,k)$-line game if she can stop Bob from getting $k$ blue points in a row.

Relabel the balls $1,2,\cdots, m.$ Our claim is that Alice wins if the starting position has no more than $k-2$ balls among $2,3,\cdots, m-1$ colored blue, unless $k=m$ and both endpoints are also colored blue. This is easily proved by induction, with Alice making a non-endpoint move adjacent to a blue point. This implies our lemma, as $m=n-k$ cannot equal $k$ due to $n$ being odd.

Answer 3

Here is the Java code I used to simulate the game. Feel free to reuse it or translate it into another programming language.

The value of $n$ is taken from the program arguments. On my 2013 MacBook Pro, it can prove the first player wins for odd $n$ up to 19 (that takes 2-3 minutes). The runtime increases exponentially for higher $n$ and it's not really optimized. It's programmed in the same way as endgame tablebases for chess; you start with (final) positions you know are winning for the first player. You retract the last move; for the first player, you're looking at moves which will reach a winning position (those are losing positions for the second player); for the second player, you're looking at positions in which all moves will reach a losing position (those are winning positions for the first player). You continue moving backwards until you reach the starting position, or no 'new' positions are left to consider.

package net.mathoverflow.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// https://mathoverflow.net/q/298443/70594
public class CircleGame {
    private static int n;
    // A 'board' is represented by an array of n numbers having one of the values below.
    // The first player is 'white', the second player 'black'.
    private static final short WHITE = 1, EMPTY = 0, BLACK = -1;

    public static void main(String[] args) throws Exception {
        // Determine the board size from the program argument
        n = Integer.parseInt(args[0]);
        if (n > 39) {
            // 3^40 > 2^63 (the size of a long) so the unique code generation might not be unique anymore.
            throw new Exception("Maximum board size is 39.");
        }

        // First, we need to determine which final positions are won for white and which aren't.
        // We are going to enumerate all final positions by first concentrating on the positions
        // of the white nodes.
        // We can assume WLOG White starts at 0; this is move 0.
        short[] initialBoard = new short[n];
        initialBoard[0] = WHITE;
        populateFullBoards(initialBoard, 0, (n - 1) / 2);

        List<short[]> newBoardsToConsider = new ArrayList<>();
        int move = n / 2;

        do {
            if (move == n / 2 && n % 2 == 0) {
                // Black is making the last move, skip the white part in the first loop
            } else {
                System.out.println(currentBoardsToConsider.size() + " positions losing for Black on move " + move);
                if (currentBoardsToConsider.isEmpty()) {
                    break;
                }

                // White to move; currentBoardsToConsider contains positions which are losing for Black with Black to
                // move. Therefore, we need to look for boards where White can reach one of currentBoardsToConsider
                // with a single move.
                for (short[] board : currentBoardsToConsider) {
                    for (int i = 1; i < n; i++) {
                        if (board[i] != WHITE)
                            continue;
                        // White can win by moving to i as last move
                        short[] newBoard = Arrays.copyOf(board, n);
                        newBoard[i] = EMPTY;
                        // Already known?
                        long code = getUniqueCode(newBoard);
                        if (results.containsKey(code))
                            continue;
                        results.put(getUniqueCode(newBoard), WHITE);
                        newBoardsToConsider.add(newBoard);
                    }
                }

                // Prepare Black's move
                currentBoardsToConsider = newBoardsToConsider;
                newBoardsToConsider = new ArrayList<>();
            }
            System.out.println(currentBoardsToConsider.size() + " positions winning for White on move " + move);
            if (currentBoardsToConsider.isEmpty()) {
                break;
            }

            // Black to move; currentBoardsToConsider contains positions which are losing for Black with White to
            // move. Therefore, we need to look for boards where Black can reach only these losing positions,
            // whatever they move.
            for (short[] board : currentBoardsToConsider) {
                for (int i = 1; i < n; i++) {
                    if (board[i] != BLACK)
                        continue;
                    // Undo last move
                    short[] newBoard = Arrays.copyOf(board, n);
                    newBoard[i] = EMPTY;
                    // Already known?
                    long code = getUniqueCode(newBoard);
                    if (results.containsKey(code))
                        continue;
                    // Try all black moves (except i which we already know loses)
                    boolean isLosing = true;
                    for (int j = 1; j < n; j++) {
                        if (board[j] != EMPTY || j == i)
                            continue;
                        // Move to j
                        short[] newNewBoard = Arrays.copyOf(newBoard, n);
                        newNewBoard[j] = BLACK;
                        Short result = results.get(getUniqueCode(newNewBoard));
                        if (result == null || result != WHITE) {
                            isLosing = false;
                            break;
                        }
                    }

                    // Losing?
                    if (!isLosing)
                        continue;
                    results.put(code, WHITE);
                    newBoardsToConsider.add(newBoard);
                }
            }

            // Prepare White's move
            currentBoardsToConsider = newBoardsToConsider;
            newBoardsToConsider = new ArrayList<>();
            move--;
        } while (move > 0);

        if (move == 0) {
            System.out.println(currentBoardsToConsider.size() + " positions losing for Black on move " + move);
        }
    }

    private static List<short[]> currentBoardsToConsider = new ArrayList<>();
    private static Map<Long, Short> results = new HashMap<>();

    private static long getUniqueCode(short[] board) {
        // For the unique code of the board, we add 1 to all board values and interpret the result as a ternary number
        // (node 0 is the lowest (i.e. '1') digit, node 1 is the '3' digit etc.).
        long power = 1, code = 0;
        for (int i = 0; i < n; i++) {
            code += power * (board[i] + 1);
            power *= 3;
        }
        return code;
    }

    private static void populateFullBoards(short[] board, int lastWhiteMove, int movesLeft) {
        if (movesLeft == 0) {
            // We've positioned all white nodes; the remaining are black nodes
            for (int i = 1; i < n; i++) {
                if (board[i] == EMPTY)
                    board[i] = BLACK;
            }
            // Determine the result of the game
            short result = determineResult(board);
            if (result == WHITE) {
                currentBoardsToConsider.add(board);
            }
            results.put(getUniqueCode(board), result);
            return;
        }

        // Recursive part
        for (int i = lastWhiteMove + 1; i <= n - movesLeft; i++) {
            short[] newBoard = Arrays.copyOf(board, n);
            newBoard[i] = WHITE;
            populateFullBoards(newBoard, i, movesLeft - 1);
        }
    }

    private static short determineResult(short[] board) {
        int longestWhiteRun = 0;
        int longestBlackRun = 0;
        int currentRun = 1;
        short currentSide = WHITE;
        for (int i = 1; i < n; i++) {
            if (board[i] == currentSide) {
                currentRun++;
            } else {
                // Check if this run is the longest run (so far) for this side
                if (currentSide == WHITE && currentRun > longestWhiteRun) {
                    longestWhiteRun = currentRun;
                }
                if (currentSide == BLACK && currentRun > longestBlackRun) {
                    longestBlackRun = currentRun;
                }
                // Reset current run
                currentRun = 1;
                currentSide = board[i];
            }
        }
        // If the last node is black, the current run ends there
        if (currentSide == BLACK && currentRun > longestBlackRun) {
            longestBlackRun = currentRun;
        }

        // If not, the longest white run might stretch over the end of the array
        if (longestWhiteRun > longestBlackRun)
            return WHITE;
        if (currentSide == WHITE) {
            for (int i = 0; i < n; i++) {
                if (board[i] != WHITE)
                    break;
                currentRun++;
                if (currentRun > longestBlackRun)
                    return WHITE;
            }
            if (currentRun > longestWhiteRun) {
                longestWhiteRun = currentRun;
            }
        }
        return (longestBlackRun > longestWhiteRun) ? BLACK : EMPTY;
    }
}

Answer 4

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.