Primer un montón Nim

Question

He estado trabajando en un problema interesante que mi profesor mencionó recientemente. El Prime Nim es una variante del juego Nim en la que se tiene una sola pila con un número arbitrario $n\in \Bbb N+\{0\}$ de elementos y los jugadores pueden llevarse un número primo de elementos en cada ronda. Ahora quiero encontrar una manera de decidir si podemos asegurar la victoria en una posición determinada (y la estrategia ganadora, por supuesto).

Lo que he hecho hasta ahora:

$0$ y $1$ son posiciones claramente perdidas. Por el contrario, cualquier primo $n$ y $n+1$ son posiciones ganadoras. Para todos los demás $n$ podemos decir que si no hay ningún primo $p<n$ tal que $n-p \notin \{n'|n'<n \land n' \text{ is lost}\}$ entonces $n$ es una posición perdedora. El conjunto de posiciones perdedoras puede expresarse más formalmente de forma recursiva, basándose en conjuntos anteriores de este tipo para posiciones más pequeñas $n$ . (En otras palabras, se trata de una aplicación de la idea muy básica de que una posición de la que no podemos hacer ningún movimiento es una posición perdedora). Todas las demás posiciones son posiciones ganadoras. Muy sencillo y general.

Las posiciones perdedoras pueden describirse como una secuencia - http://oeis.org/A025043 (curiosamente una subsecuencia de http://oeis.org/A093513 ). Esto utiliza la naturaleza recursiva del problema.

Un algoritmo que parte del caso de borde de recursión ( $0$ ) y construir la secuencia progresivamente puede darnos tanto la respuesta como la posible estrategia ganadora generada como producto secundario en tiempo polinómico.

Mi profesor dijo que el algoritmo de búsqueda de estrategias es probablemente óptimo, pero también sugirió que podría haber una fórmula sencilla para decidir si se puede ganar una posición determinada utilizando una estrategia óptima.

Y ahora estoy atascado en él. Supongo que la fórmula no puede ser que simple, ya que tiene que incluir, en mi opinión, al menos la prueba de primalidad. He intentado determinar una forma sencilla de decidir si un número está en la secuencia de posiciones perdedoras, pero no he tenido éxito hasta ahora. Básicamente, siempre me encuentro con el impenetrable problema de generar $n$ el primero.

¿Alguna idea para enfocar esto de otra manera?

Answer 1

¿Incluye usted $1$ como un movimiento razonable? Si es así, este juego ("Prime Nim" creado por CE Shannon) ha sido resuelto .

Si no es así, en el artículo anterior Martin Gardner afirma que un análisis de la estrategia sería muy difícil.

Answer 2

La falta de información adicional con la secuencia OEIS puede indicar que la estrategia no es "simple". Sin embargo, he aquí algunas heurísticas:

Según los datos de la OEIS, 10000 números hasta 67673 son perdedores, es decir, más que $\frac17$ y prácticamente todos ellos son Impares (sólo veo las excepciones $0, 10, 34, 100, 310$ ). Heurísticamente, este sobrepeso de impar continuará: Supongamos que hay $a$ impar y $b$ números pares de perdedores $x_i<N$ con $a\gg b$ . Entonces, si $N$ está en empate, es un perdedor si ninguno de los $a$ Números de impar $N-x_i$ es primo. Esta probabilidad podría ser algo así como $$p_{\text{even}}=\left(1-\frac2{\ln N}\right)^a\approx e^{-\frac{2a}{\ln N}}.$$ Por otro lado, si $N$ es impar, es un perdedor sólo si $N-2$ no es un perdedor (que vamos a ignorar) y ninguno de los $b$ Números de impar $N-x_i$ es primo, que debería ser algo así como $$p_{\text{odd}}=\left(1-\frac2{\ln N}\right)^b\approx e^{-\frac{2b}{\ln N}}.$$ Según los datos empíricos, parece que $b$ es de un tamaño comparable al de $\ln N$ Por lo tanto $p_{\text{odd}}$ es de un tamaño "razonable" (no se acerca realmente a $0$ ), por lo que $a\approx p_{\text{odd}} N$ de tamaño comparable a $N\gg\ln N$ que hace que $p_{\text{even}}$ casi insignificante.

Supongo que un argumento similar podría indicar que la "mayoría" de los números perdedores no son divisibles por 3 o, de hecho, por ningún primo $p\ll N$ (quizás más bien $p\ll \ln N$ ?).

Pero todo esto está lejos de dar una simple Definitivamente respuesta a si un particulyr $N$ es un perdedor o un ganador ...