Teoría de los juegos: Conexión de puntos en un círculo

Question

"Tienes 21 puntos en un círculo y en cada turno un jugador puede conectar dos puntos cualesquiera con una cuerda que no se cruce con ninguna otra (¡ni siquiera en los puntos finales!). El jugador que no pueda moverse pierde".

Quiero resolver este problema para un número general de impar.

Progreso: Está claro que P1 gana si hay un número par de puntos - dibujar un diámetro y utilizar la simetría. Sin embargo, no está claro qué ocurre con un número impar de puntos.

Tenga en cuenta que una jugada divide la partida en dos juegos independientes. Sin embargo, como el juego es imparcial, dividir una partida en dos posiciones ganadoras no garantiza una victoria. Intenté trabajar hacia atrás y traté de considerar los casos en los que P1 o P2 pueden forzar una victoria O una derrota. Por ejemplo, para $n = 4$ P1 puede forzar tanto una victoria como una derrota.

Mi escollo con este planteamiento es que un jugador puede elegir empezar a jugar una partida ganadora en uno de los juegos pero luego cambiar de opinión y empezar a jugar una partida perdedora y puede ocurrir que en ese momento pueda forzar ambas. Se agradece cualquier ayuda.

Answer 1

Dejemos que $v(n)$ sea el valor nim del juego para $n$ puntos. Entonces tenemos $v(0)=v(1)=0$ , $v(2)=1$ y la siguiente relación recursiva para $n\geq 3$ : $$v(n)=\textrm{mex}\{v(k)+v(n-2-k):0\le k \le n-2\}$$ donde $\textrm{mex}$ es el elemento mínimo excluido función.

Aquí están los primeros valores:

0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4
0 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 2 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
8 1 1 2 0 3 1 1 0 3 3 2 2 4 4 5 5 9 3 3 0 1 1 3 0 2 1 1 0 4 5 3 7 4
...

El patrón se repite en un periodo de $34$ y las posiciones perdedoras son exactamente aquellas en las que $$n \equiv 5,9,21,25, \textrm{or } 29 \pmod{34},$$ así como (curiosamente) $n = 1, 15$ y $35$ .

---

Código

Aquí está el código Ruby que escribí (tenga en cuenta que no soy un programador, así que estoy seguro de que hay formas mucho mejores de hacer esto):

$stored_v = [nil]   # store previously calculated values of v so that
                    #  we don't have to recursively calculate them every time

def mex(l)          # mex (minimal excluded element) of a list l
    ls = l.sort.uniq

    for i in 0..ls.size do
        if i != ls[i] then
            return i
        end
    end
    return ls.size
end

def v(n)            # nim-value of a game with n points
    if $stored_v[n] != nil then
        return $stored_v[n]
    end

    if n <= 1 then
        $stored_v[n] = 0
        return 0
    elsif n <= 3 then
        $stored_v[n] = 1
        return 1
    else
        l = []
        for k in 0...n-2 do
            l = l + [v(k) ^ v(n-2-k)]   # bitwise XOR (i.e., nim sum) of
                                        #  games on k and n-2-k points
        end
        $stored_v[n] = mex(l)
        return mex(l)
    end
end