Solución matemática simple juego

Question

Considere el siguiente juego (que yo). Dos jugadores cada uno intentan nombre de un número de destino. El primer jugador comienza nombrando a 1. En cada turno, un jugador puede nombrar a cualquier número mayor que difiere de la actual número por un divisor del número actual, incluyendo a sí mismo. Por ejemplo, si el actual número 6, el siguiente número de la llamada podría ser cualquiera de los 7, 8, 9, o 12. Un jugador que se nombra a la meta gana. Un jugador obligado a nombrar un número mayor que el número de destino pierde.

Si el número es impar, el primer jugador puede ganar trivialmente por siempre nombrando a un número impar, porque la diferencia entre el número actual y el número de destino es aún, y ningún número impar tiene un divisor. La cosa me parece que no puede averiguar es si el primer jugador también tiene una estrategia ganadora para cada número mayor que 6, y lo que la estrategia se si es así. Obviamente, uno puede determinar el curso óptimo de juego para cualquier número de destino trabajando hacia atrás, y al hacerlo parece sugerir que el primer jugador puede ganar siempre, pero no he sido capaz de entender por qué.

Es allí cualquier manera de probar que el primer jugador puede ganar siempre para cualquier número mayor que 6?

Answer 1

No una respuesta.

Para aquellos que quieren ver la nimbers de estos juegos, he escrito el siguiente código, el cual calcula la nimbers para los juegos con el objetivo de $N$ de $2$ a $999$.

Cómo usarlo:

ir a este sagecell página y pegar el siguiente texto, a continuación, presione el botón "Evaluar".

def Nim(N):
    a = [0] * (N + 1)
    maxNim = 4
    for i in range(N - 1, 0, -1):
        f = [False] * maxNim
        for d in divisors(i):
            if i + d > N: continue
            f[a[i + d]] = True
        j = 0
        while j < maxNim:
            if f[j] == False: break
            j += 1
        f = []
        a[i] = j
        if j == maxNim: maxNim *= 2
    return a

for n in range(2, 1000):
    print(n, Nim(n)[1:])

Cada línea de la salida se parece a esto:

(4, [0, 2, 1, 0])

Esto significa: si el número de destino es $4$, luego de que un jugador se enfrenta número $1, 2, 3, 4$ ha nimber $0, 2, 1, 0$, respectivamente.

---

Parece que no está claro si mi comentario anterior acerca de la convergencia de $\{n(N, M)\}_N$ es correcta.

A $N = 999$:

la secuencia de $\{n(N, 2)\}$ parece converger después de $N = 72$;

la secuencia de $\{n(N, 4)\}$ parece converger después de $N = 282$;

la secuencia de $\{n(N, 6)\}$ parece converger después de $N = 160$.

Sin embargo:

la secuencia de $\{n(N, 8)\}$ sólo converge después de $N = 910$.

Así que es justo decir que aún no está claro si $\{n(N, 8)\}$ converge.

Cosas similares suceden con $\{n(N, 16)\}$ etc.

Answer 2

Creo que cada objetivo mayor que $6$ es de hecho un primer triunfo de jugador. No tengo ninguna prueba, pero presentes en la evidencia y la especulación sobre lo que podría conducir a una prueba.

Para cada objetivo, al menos hasta $10000$ hay una estrategia que es $2k \rightarrow 2k+1$ , excepto para una pequeña lista de excepciones. Por ejemplo

• Objetivo $T=9580$

  Estrategia: El otro jugador siempre estado a pesar de los números. Nuestra respuesta debe ser $2k \rightarrow 2k+1$ , con estos cuatro excepciones $$4786 \rightarrow 7179,\ 7184 \rightarrow 7633,\ 9100 \rightarrow 9105,9572 \rightarrow 9574,\ 9578\rightarrow 9580$$

Permitanme que lo justifique. Considere los conjuntos $$W=\{9574,9580\}$$ $$L=\{4787,7185,9101,9573,9575,9579\}$$

Estos son los números que es un ganador para el estado y los números impares que es un perdedor a estado. Si el oponente nunca los estados miembro de $W,$ que no pueden ganar. Pero esas son las $T=2^2\cdot 5\cdot 479$ e $9574=2\cdot 4787 .$ Si nunca hemos estado los números impares $9579,9575,9101,7185=T-1,T-5,T-479,T-2395$ o $4787=9574-4787,$ no dice nada de $W$ , a menos que tal vez hemos estado un número par. Podríamos decir que la $9580$ y ganar. Y si hemos estado $9574=2\cdot 4787$ que sólo puede responder $9576$ a los que podemos respuesta $9577 \notin L.$ , Así que sólo necesita las respuestas de otros de $2k \rightarrow 2k+1$ para $2k+1 \in L.$ Así que preferiblemente $2k \rightarrow 2k+t\lt T$ donde $t \gt 1$ es un divisor impar de $k$ e $2k+t \notin L$. Y hemos hecho esto para cuatro de los cinco casos.Para $9573-1=9572=2^2\cdot 2393$ no hay tal $t$ a utilizar. Afortunadamente, $9572 \rightarrow 9574$ nos permite declarar un ganador.

OPCIONAL DIGRESIÓN: he Aquí tres ejemplos más

• objetivo $T=2^j$:

  Estrategia: $2k\rightarrow 2k+1$ excepto $2^k-2 \rightarrow 2^k.$ Lo $W=\{2^k\}\ \ L=\{2^k-1\}.$

• objetivo $T=2p$ para $p$ principales, pero no un Fermat prime $p=2^s+1.$

  Estrategia: $2k \rightarrow 2k+1$ excepto $2p-2 \rightarrow 2p$ e $p-1 \rightarrow p-1+t$ donde $t \gt 1$ es el siguiente menor divisor impar. Por lo $W=\{2p\}\ \ L=\{p,2p-1\}.$

Desde $p-1$ no es una potencia de $2,$ no es un divisor impar.

• objetivo $T=2p$ para $p$ un Fermat prime $p=2^s+1:$

  Estrategia: $2k \rightarrow 2k+1$ excepto $2p-2 \rightarrow 2p$ e $p-3 \rightarrow p-3+t$ donde $t\gt 1$ es el siguiente menor divisor impar (también lo $t \gt 3.$). aquí $W=\{p-1,2p\}\ \ L=\{p,2p-3\}.$

Desde $p-1=2^s$ es en realidad incluso un ganador como el único respuestas $p$ , e incluso los perdedores.

FIN DE LA DIGRESIÓN

La pregunta que se plantean son:

• ¿Cómo hemos llegado con el (o un) estrategia válida?

• ¿Cómo podemos descartar $1 \in L?$

• Cuán grande sería el conjunto de excepciones?

---

Los métodos para lograr un objetivo $T=2n$ es empezar a $W=\{2n\}$ e $L=\{\}$ donde $W$ será el que incluso los ganadores y $L$ va a ser la excepción, perdedores.

Mientras que hay no examinadas miembros de $W \cup L$, considera el más grande.

• Si es $2k \in W$, a continuación, agregue $2k-t$ a $L$ donde $t$ rangos de los divisores impares de $k$. A continuación, recoger la siguiente examinar los estados.

• Si es $2f+1 \in L$ , a continuación, encontrar una buena respuesta a la $2f$ o, si no hay ninguno, agregar $2f$ a $W$: Considere la posibilidad de $2f+t$ donde $t$ pasa a través de los divisores de $2f$, tan pronto Como usted consigue incluso un ganador en $W$ o y un número impar no en $L$, añadirá a tu lista de reglas excepcionales. Si ninguno de esos suceder, agregar $2f$ a $W.$ , a Continuación, recoger la siguiente examinar los estados.

Parar cuando todo en la actualidad en $W \cup L$ ha sido examinado.

---

Las excepciones, dado aún una meta $T \gt 6$, se $W,$ los números pares es un ganador al estado y a $L$ los números impares es un perdedor a estado. Para $\mathcal{T}$ un conjunto de incluso objetivos (como todos los números enteros mayores que $6$), Una manera de demostrar que todos los $T \in \mathcal{T}$ es un primer triunfo de jugador es mostrar que todos los $T \in \mathcal{T}$ tiene más pequeña excepción $e \gt 1$.

Un fuerte resultado podría ser más fácil. Yo conjetura de que $e \gt \frac{T}{4}.$

Incluso para $6 \lt T \lt 10000$ hay $114$ de los casos donde la $\frac{e}{T} \lt \frac{15}{41}.$ Aquí están los primeros pares de $[T,e]$ si se ordena de acuerdo a una relación cada vez mayor $\frac{e}{T}$

$$[114,31],[10,3],[30,9],[462,151],[130,43],[450,151],[1254,421],[2058,691],[1250,421],[3654,1231],[2050,691],[2530,853],[3650,1231],[4930,1663],[5730,1933],[8454,2851],[8450,2851],[9250,3121],[9570,3229]$$

Por lo $\frac{e}{T} \gt \frac14$ (a $T=10000$) y $\frac{e}{T} \gt \frac13$ para $T \gt 130.$ Por otro lado, hay $T$ sobre el borde de la examinó con rango $\frac{e}{T} \lt 0.337$

---

Hay $12$ de los casos de $4 \leq T \leq 10000$ con $2$ excepciones, los poderes de La $2.$

Sin embargo, hay $1285$ con un excepcional conjunto de tamaño $3$, todos los casos de $T=2p$ y en algunos, pero no todos, $T=2^sp$ grandes $s.$

Aquí están los primeros recuentos: $$[2, 12], [3, 1285], [4, 28], [5, 609], [6, 187], [7, 60], [8, 525].$$ El más grande de la $72,75,80,83,84,94,97$ que se producen una vez cada uno.

Aquí es un acumulativa de la parcela

Tan sólo en virtud de $\frac23$ de los casos excepcionales conjuntos de tamaño $12$ o menos y más de $90\%$ han excepcional conjunto de tamaño $25$ o menos.

---

Sólo puede decir que el objetivo es el número más grande que puede ser enunciada y el primer jugador sin mover pierde. Yo no considerar el caso de la primer jugador sin un movimiento gana, pero debe de ser en gran medida similares.