Alice y Bob jugando en círculo

Question

Quiero resolver este problema:

Vamos a no ser $n \ge 2$ puntos alrededor de un círculo. Alice y Bob jugar a un juego en el círculo. Ellos toman mueve a su vez con Alice principio. En cada movimiento:

• Alice lleva a un punto que no ha sido de color antes y colores de rojo.

• Bob lleva a un punto que no ha sido de color antes y colores de azul.

Cuando todos los $n$ puntos han sido de color:

• Alice encuentra el máximo número consecutivo de puntos rojos en el círculo y llamar a esta $R$.

• Bob se encuentra el máximo número de consecutivo de puntos azules en el círculo y llamar a esta $B$.

Si $R \gt B$, Alicia gana. Si $B \gt R$, Bob gana. Si $R = B$, nadie gana. ¿Alice tiene una estrategia ganadora para el extraño $n$?

Todavía nos parece que no sé por que extraña $n$ Alice tiene una estrategia ganadora. Ella hace por $n=3$, y parece que también para $n=5$. Pero en general, no estoy seguro. Podría alguien ayudar?

Answer 1

Incluso para $n$, afirmo que nadie tiene una estrategia ganadora, y por lo tanto ambos jugadores tienen el dibujo de las estrategias.

Para ver esto, observe primero que por el teorema fundamental de finito de juegos, sabemos que uno de los jugadores tiene una estrategia ganadora, o ambos jugadores tienen el dibujo de las estrategias.

A continuación, me afirmación de que Bob tiene un dibujo de estrategia, que es simplemente el uso de la copia de la idea de usuario Mohemnist en los comentarios. Él simplemente par de vértices opuestos y hacer que el color de la anti-simétrica. De esta manera, la cadena de rojo los vértices se corresponde con una simétrica cadena de azul vértices, y por lo tanto Bob puede asegurar que no vaya a perder.

Pero ahora, se deduce que Bob no tiene una estrategia ganadora, ya que Alice puede pretender ser Bob por una estrategia de robo de argumento. Básicamente, esto equivale a la observación de que no puede ser ventajoso para ir segundo. Es decir, Alice puede empezar simplemente por la coloración cualquier vértice rojo, y a partir de entonces pretender ser el segundo jugador, siguiendo la estrategia ganadora para Bob, pero con intercambian los colores. Si esa estrategia nunca debe dirigir su color de la ya de color de vértice, entonces ella puede simplemente tomar otro movimiento libre.

Hemos demostrado que Bob tiene un dibujo de estrategia y no tiene una estrategia ganadora. De ello se desprende que Alice no tiene una estrategia ganadora, y por lo tanto debemos ser en el caso del teorema fundamental donde ambos jugadores tienen el dibujo de las estrategias.

La estrategia de robo argumento funciona independientemente de si $n$ es par o impar, mostrando que Bob nunca se tiene una estrategia ganadora. Pero, por supuesto, ya sabía que esta en el extraño caso, ya que Mohemnist mostró en el caso de que Alice tiene un dibujo de la estrategia.

Answer 2

Aquí es un argumento que Alicia gana por extraño $n$. Etiqueta los puntos de $1$ a $n.$

Lema: Si en algún punto de Alice ha marcado $k$ puntos en una fila y no otros puntos, Bob ha marcado los dos puntos inmediatamente al lado de los $k$ en puntos y $k\geq 3$, entonces Alice tiene una estrategia ganadora.

La admisión de este lema, Alice puede ganar el juego original por jugar de la siguiente manera: en Primer lugar, ella marca de la bola de $2$. Si Bob no marca un punto próximo a ella, entonces ella hace las marcas adyacentes a sus anteriores se mueve hasta que Bob sus bloques a ambos lados, en cuyo caso estamos ahora en la etapa de las anteriores Lema (con $k\geq 3.$) Por otro lado, si Bob, el segundo paso es decir, la bola de $1$, entonces Alice marcas de bola de $4$. Si Bob no responde marcando $3$, entonces Alice se mueve a $3$, y se repite la estrategia anterior para terminar en la situación de la Lema. Otra cosa, si Bob marcas de punto de $3$, entonces las bolas $2$ e $3$ básicamente no hacer nada y terminamos en la situación de un juego de $n-2$ puntos donde Bob, el segundo paso es adjaent a Alice, la cual es una victoria por inducción.

La prueba del Lema: Somos esencialmente en la situación de un juego con $n-k$ bolas en una línea, en la que los dos extremos son el azul y Bob ha marcado $k-2$ otras bolas azules. Alice objetivo aquí es dejar de Bob de llegar $k$ azul bolas en una fila.

Para capturar esta situación, vamos a definir un $(m,k)$-línea de juego para ser un juego con $m$ bolas en una fila, algunos de los cuales inicio de azul, y Alice (que se mueve primero) y Bob alternando entre rojo y azul de las marcas. Alicia gana en un $(m,k)$-línea de juego si ella puede dejar de Bob de llegar $k$ azul puntos en una fila.

Re-etiquetar las bolas $1,2,\cdots, m.$ Nuestro reclamo es que Alice se gana si la posición de partida no tiene más de $k-2$ bolas entre $2,3,\cdots, m-1$ color azul, a menos $k=m$ y ambos extremos son también de color azul. Esto es fácilmente demostrado por inducción, con Alice haciendo un no-extremo mover adyacente a un punto azul. Esto implica que nuestro lema, como $m=n-k$ no puede igualar $k$ debido a $n$ que se extraña.

Answer 3

Alice tiene una estrategia ganadora para todos los impares $n$. Ya se ha observado que Alice no puede perder al $n=1,3,5$, y la siguiente construcción funcionará siempre $n\ge 5$ es impar. (Para $n$, el juego es un empate como se observa en la Mohemnist y JDH.)

La primera etapa es la misma como cardenal de la construcción: Alice intentará conseguir una línea de longitud de la $k\ge 3$. Alice comienza a jugar en cualquier lugar, y suponemos que Bob juega de modo que no se $n$ espacios a la izquierda y $m\ge n$ espacios a la derecha de Alicia jugar.

• Si $n\ge 2$, es decir,$b\_\dots\_a\_$, entonces Alice juega a la izquierda produciendo $\_aa\_$, por lo que ahora Bob no puede evitar una ejecución de longitud 3.
• Si $n=1$, es decir,$b\_a\_$, entonces Alice juega a la derecha, $b\_aa\_$, y de nuevo Bob no puede evitar una ejecución de longitud 3.
• Si $n=0$, entonces Alice juega $ba\_a\_$. Si Bob es para prevenir una carrera de longitud 3 que debe desempeñar $baba\_$, con lo cual Alice juega $baba\_a\_$ y de nuevo de Bob movimiento es forzado. Finalmente llegamos al final de la cadena, por ejemplo con un tamaño de 7 llegamos al estado de $bababa\_$ y ahora, Alice puede ganar con el único resto de mover.

Una vez que obtener al menos 3 puntos en una fila, ella sigue extender la secuencia con cada movimiento hasta que ambos extremos están bloqueados. En este punto tenemos la configuración de $b(ab)^ja^kb$, y de la $n-2j-k-2$ restante de los espacios exactamente $k-2$ ha $b$'s. Alice ahora intentará evitar Bob de llegar $k$ en una fila para ganar.

Podemos reducir, para el caso de $k=3$ mediante la eliminación de $k-3$ de Bob no juega de extremo (es decir, eliminando totalmente el punto); cualquier secuencia de longitud $3$ en el juego reducido se extenderá a $k$ en el peor.

Vamos a un "segmento" denotan un máximo de ejecución de los puntos que contiene ninguno de Alice puntos. Inicialmente, habrá una libre segmento de longitud $m=n-2j-k-2$ (más el $j$ adicional lleno de segmentos de longitud 1).

Tenga en cuenta que la situación $b\_^ib\_^jb$ donde $i$ e $j$ son ambos impares es un triunfo para Bob, porque Alice puede bloquear en la mayoría de uno de los espacios, decir la de la derecha, y luego Bob puede ganar si $i=1$, o reducir a los más pequeños de la situación $b\_b\_^{i-2}b$ donde $1$ e $i-2$ son de nuevo extraño. Esta no puede ser la inicial de la instalación debido a que esto requiere de $m=i+j+3$ a un ser extraño, pero Alice debe tener cuidado para evitar que se plantean en el juego posterior.

Durante el transcurso del juego, Alicia se juega un partido libre de segmentos y reducir su duración. Mantenemos los siguientes invariantes:

Cada segmento es "activa" o "pasiva". Cada segmento es pasivo después de que Alice se mueven, y en la mayoría de un segmento activo antes de que Alice se mueva. Hay un interior $b$ de los puntos en el segmento activo.

• Un segmento de longitud impar es pasivo, si ha $<2$ cubierto extremos y no de punto interior.
• Un segmento de longitud es pasivo, si ha $\le 2$ cubierto extremos y no de punto interior.
• Un segmento de longitud impar es activo si se ha $2$ cubierto extremos, o ha $<2$ cubierto extremos y un punto interior.
• Un segmento de longitud está activo si se tiene un punto interior.

Inicialmente, hay uno (activo) segmento de longitud, con dos extremos y un punto interior, además de cero o más pasivos de los segmentos de longitud 1.

Tenga en cuenta que en Bob mover, él puede hacer que a más de un segmento activo jugando en ella, ya sea cubriendo otro extremo, o la adición de un punto interior. Alice se mueve de la siguiente manera:

• Si todos los segmentos son pasivas, Alice se mueve en cualquier lugar. Esto no afecta a la pasividad de los segmentos, ya que no puede crear nuevos puntos del interior, y no se puede crear cualquier segmento con dos extremos bien.
• Si el activo segmento de longitud impar y no de punto interior, decir $ab\_^iba$ donde $i$ es impar, entonces Alice juega $aba\_^{i-1}b$, la producción de dos segmentos pasivos.
• Si hay un punto interior en el segmento activo, decir $a\underline{b}\_^ib\_^j\underline{b}a$ cuando la $\underline{b}$ pueden $b$ o en blanco.
  • Si $i$ es impar y $j$ es incluso (espejo para el otro caso), jugamos $a\underline{b}\_^{i-1}ab\_^j\underline{b}a$, produciendo una longitud impar segmento pasivo con un extremo de la izquierda, y en una longitud de segmento pasivo con $\le 2$ extremos de la derecha.
  • Si tanto $i$ e $j$ son impares, entonces el segmento de longitud impar, así que uno de los extremos no está presente, decir $a\underline{b}\_^ib\_^{j+1}a$. En este caso jugamos $a\underline{b}\_^{i-1}ab\_^{j+1}a$ la producción de dos de longitud impar pasivos de los segmentos con más de un extremo de cada uno.
  • Si tanto $i$ e $j$ son iguales, entonces el segmento de longitud impar, así que uno de los extremos no está presente, decir $a\underline{b}\_^ib\_^{j+1}a$. En este caso jugamos $a\underline{b}\_^iba\_^ja$ la producción de dos de longitud pasivos de los segmentos en la mayoría de los dos puntos extremos de la izquierda y no hay puntos en la derecha.

Desde estas obras preservar la hipótesis inductiva, continuamos hasta que el juego termina, después de la de Alice de vuelta. Esto significa que cada segmento es pasivo, sino un segmento pasivo con ningún espacio libre es de longitud 1 (si la longitud impar) y de longitud 2 (si aún longitud), por definición, así que Bob no pudo hacer un tres en una fila y Alicia gana.

Answer 4

Aquí está el código Java que he utilizado para simular el juego. Siéntase libre de reutilizarlos o traducir a otro lenguaje de programación.

El valor de $n$ es tomado de los argumentos de programa. En mi 2013 MacBook Pro, puede ser el primer jugador gana por extraño $n$ hasta 19 (2-3 minutos). El tiempo de ejecución aumenta de forma exponencial para mayor $n$ y no es realmente optimizado. Se programan de la misma manera como endgame tablebases para el ajedrez; se comienza con (final) de las posiciones que usted sabe que son ganadora para el primer jugador. Retrae el último movimiento; para el primer jugador, usted está buscando en los movimientos que se llegará a una posición ganadora (aquellos que están perdiendo posiciones para el segundo jugador); para el segundo jugador, usted está buscando en las posiciones en que todo se va a llegar a una posición perdedora (esas son las posiciones ganadoras para el primer jugador). Continúa avanzando hasta llegar a la posición de partida, o no 'nuevo' posiciones de izquierda a considerar.

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;
    }
}