¿Cuál es la estrategia óptima en el "Factor Game"?

Question

Editar (1 de noviembre de 2015): Recompensa otorgada, pero la pregunta completa (es decir, cuál es la estrategia óptima) permanece abierta en el momento de esta actualización.

---

Considera el Juego de Factores que se juega de la siguiente manera:

Dada una lista de enteros positivos $1, \ldots, n$, dos jugadores (rojo y azul) se turnan para jugar.

En cada turno, el jugador elige y rodea (con su color) cualquier número sin rodear $k$ que tenga al menos un divisor propio aún por rodear; su oponente responde rodeando (con su propio color) todos los divisores propios restantes de $k.

Luego intercambian (los colores se ajustan en consecuencia) y el juego continúa hasta que ya no quedan movimientos legales.

En ese momento, cada jugador suma los números rodeados y el mayor sumatorio gana.

Pregunta: ¿Cuál es la estrategia óptima en el Juego de Factores?

Mi suposición es que, para un $n$ lo suficientemente grande, elegir el número que genere más puntos en cada turno individual es óptimo. Por ejemplo, si $n = 49$, entonces el primer jugador elegiría $47$ (para generar $46) y su oponente respondería con $49$ (para generar $42). Pero esta estrategia es admitidamente a corto plazo.

(Claramente la estrategia falla para algunas elecciones pequeñas de $n$ (el ejemplo de $n = 4$ se proporciona en los comentarios; $n = 9$ es otro fallo) pero estoy de acuerdo en suponer que $n$ es suficientemente grande).

Espero una descripción de una estrategia óptima y una prueba de que es óptima (para $n$ lo suficientemente grande), pero estaría interesado en casos especiales, argumentos heurísticos sobre cuál sería una estrategia óptima, y argumentos heurísticos sobre por qué este problema es difícil.

---

Motivación: Este juego a veces se juega en escuelas primarias (o, en mis clases, con profesores de escuela primaria) para explorar conceptos como primo, compuesto, divisor, divisor propio, etc. En tal caso, los números suelen presentarse en un arreglo - a menudo un arreglo cuadrado, y por lo tanto mi interés particular es cuando $n$ es un cuadrado.

Puedes jugar al Juego de Factores a través del sitio de Illuminations del NCTM (Consejo Nacional de Profesores de Matemáticas) si deseas experimentarlo por ti mismo.

Aquí tienes un tablero de muestra cuando $n = 49$ (presentado como un arreglo de $7 \times 7):

Answer 1

Limpieza en ediciones anteriores

La estrategia codiciosa puede ser descrita, como se indica en el post original, para n lo suficientemente grande, como la selección localmente óptima de números para obtener la mayor cantidad de puntos en cada turno individual.

Esto falla para $1\leq n\leq 500$ para los siguientes n:

$$4, 9, 25, 28, 29, 42, 52, 53, 54, 58, 59, 60, 61, 66, 77, 86, 102, \ 103, 104, 108, 109, 114, 115, 117, 122, 123, 161, 162, 176, 177, 182, \ 183, 184, 185, 187, 189, 194, 195, 210, 211, 216, 217, 221, 228, 229, \ 238, 239, 243, 245, 247, 248, 249, 273, 282, 283, 286, 287, 288, 289, \ 292, 293, 298, 310, 311, 312, 313, 324, 325, 330, 331, 333, 338, 339, \ 343, 344, 345, 350, 351, 354, 355, 363, 364, 365, 369, 374, 375, 376, \ 382, 383, 384, 385, 387, 391, 392, 395, 396, 397, 405, 407, 408, 409, \ 412, 413, 414, 415, 420, 421, 429, 432, 433, 436, 437, 442, 443, 444, \ 445, 452, 453, 458, 466, 467, 477, 482, 487, 488$$

En estos casos (donde para la estrategia codiciosa original, se elegiría el primo más alto en el rango para abrir el juego), se seleccionará el semiprimo impar más alto en el rango. A partir de la elección inicial, se juega con la estrategia codiciosa. Esta estrategia resulta en una victoria para el jugador $1$ para todos los $n\leq 500.$

Con este enfoque, es posible evitar el juego de "jugar bajo" descrito a continuación, junto con sus peligros obvios.

Utilizando el código de MMA en el siguiente enlace, uno puede encontrar todos los números iniciales que dan una victoria para el jugador uno (y luego jugar según la estrategia localmente óptima). Tomando $n=25$, por ejemplo, que no da una victoria usando la estrategia local óptima,

With[{nn = 25}, 
Select[Transpose@{Range[2,nn],c4R[s1,nn,#] &/@ Range[2, nn]}, #[[2]] > 0&]]

%[[All, 1]]

da $5, 7, 11, 25$ (por lo tanto, se elige $25$ como el primer juego ya que es el semiprimo impar más grande en el rango dado) como los números iniciales ganadores para el jugador $1$.

De igual manera, probando los números que fallan en las aperturas de primos:

With[{nn = #}, c4R[s1, nn, Max@Select[Range@nn, OddQ@# == True && 
PrimeOmega@# == 2 &]]] & /@ {9, 25, 28, 29, 42, 52, 53, 54, 58, 59, 60, 61, 
66, 77, 86, 102, 103, 104, 108, 109, 114, 115, 117, 122, 123, 161, 162, 176, 
177, 182, 183, 184, 185, 187, 189, 194, 195, 210, 211, 216, 217, 221, 228, 
229, 238, 239, 243, 245, 247, 248, 249, 273, 282, 283, 286, 287, 288, 289, 
292, 293, 298, 310, 311, 312, 313, 324, 325, 330, 331, 333, 338, 339, 
343, 344, 345, 350, 351, 354, 355, 363, 364, 365, 369, 374, 375, 376, 
382, 383, 384, 385, 387, 391, 392, 395, 396, 397, 405, 407, 408, 409, 
412, 413, 414, 415, 420, 421, 429, 432, 433, 436, 437, 442, 443, 444, 
445, 452, 453, 458, 466, 467, 477, 482, 487, 488}

da todos valores positivos.

Respuesta original

Modificar la primera elección a $2$ (en lugar del primo más alto en el rango) donde la solución "de corto alcance" falla parece ser la estrategia ganadora.

Sin embargo, esto no se cumple para $n=77$:

Select[With[{aa = Select[Transpose@{Range@200, aa}, #[[2]] < 0 &]
[[All, 1]]}, Transpose@{aa, (Sign@bb)[[#]] & /@ aa}], #[[2]] < 0 &][[All, 1]]

strat[n] para cualquier $n\geq30$ debería entonces forzar una victoria para el jugador $1$ para la mayoría de $n$. Tener en cuenta que el jugador $2$ juega la estrategia localmente óptima, pero, aunque me sorprendería si una estrategia alternativa pudiera forzar una victoria para el jugador $2$, esta posibilidad aún no se ha explorado.

Nota

Por supuesto, dado que el juego se revertirá si el jugador $1$ elige $1$ para comenzar, y al hacerlo, permite que el jugador $2$ vaya primero, si el jugador $2$ juega con la misma estrategia, elegirá $2$, etc., haciendo el juego bastante absurdo. Se debe adherir a una regla que impida a cualquiera de los jugadores renunciar a un turno, si se desea llegar a una solución sensata.

Añadido

Creo que la estrategia local resulta en el juego más largo para suficientemente grandes $n$. Curiosamente, la longitud del juego para la estrategia local para cada $n\sim n/e:$

dd = {0, 0, 0, 0}~Join~(Length@s4[s1, #, Max@Select[Range@#, PrimeQ]] & /@ 
Range[5, 200]); ListLinePlot[{dd, Range@200/E}]

---

Código de Mathematica disponible aquí.