Juego de factorización, ¿podemos encontrar una estrategia ganadora?

Question

Estoy pensando en un problema de teoría de juegos relacionado con la factorización. Aquí está,

P: dos jugadores A y B están jugando a este juego de factorización. Al principio, tenemos un número natural $270000=2^4\times 3^3\times 5^4$ en una pizarra.

en su propio turno, cada jugador elige un número $N$ de la pizarra y borrarlo, y luego escribir nuevos dos números naturales $X$ y $Y$ satisfaciendo

(1) $N=X\times Y$ (2) $gcd(X,Y)>1$ (Por lo tanto, "NO" son coprimos)

un jugador pierde si no puede realizar este proceso en su turno.

Así, en este juego, los posibles estados en $k$ -la vuelta es en realidad una secuencia de números naturales $a_1,a_2,\dots,a_k$ con $a_i>1$ y $a_1\times a_2\dots \times a_k=270000$

EJEMPLO de este juego)
El turno de A $2^{4}\times3^{3}\times5^{4}$
El turno de B $2^2\times3\times5^2,2^2\times3^2\times5^2$
El turno de A $2^2\times3\times5^2,2\times3\times5,2\times3\times5$
El turno de B $2\times5,2\times3\times5,2\times3\times5,2\times3\times5$
Así que B pierde en el caso anterior.

En realidad, en este juego, el primer jugador(Así, A) tiene estrategia ganadora.
¿Cuál es esta estrategia ganadora para A?

-Intento de acercamiento: Intenté encontrar lo que es una "posición ganadora" y una "posición perdedora" para este juego combinatorio. pero clasificar estas posiciones no era tan obvio.

¿Cuál es la estrategia ganadora de A? Gracias por cualquier ayuda de antemano.

Answer 1

Esto es Nim disfrazado. Sugiero que se represente una pila por una secuencia de los exponentes de los primos, así $270000$ estaría representado por $(4,3,4)$ A continuación, puede clasificar los números iniciales en orden, como $(4,4,3)$ jugaría exactamente igual. Una jugada legal es sustituir una secuencia por dos secuencias tales que: la suma de las posiciones correspondientes en las nuevas secuencias coincide con el número de la secuencia original y al menos una posición de las nuevas secuencias es mayor que cero en ambas. Por ejemplo, de $(4,3,4)$ puede pasar a $(2,3,4)+(2,0,0)$ o a $(3,2,1)+(1,1,3)$ o a $(4,1,2)+(0,2,2)$ pero no a $(4,3,0)+(0,0,4)$ . Usted está tratando de encontrar los valores nim de varias posiciones.

Empezaría con secuencias de una sola posición, por lo que el número original es una potencia prima. $(1)$ es una posición perdedora, también lo es $*0$ . $(2)$ es claramente $*1$ ya que tienes que moverte a $(1)+(1)$ . $(3)$ está perdiendo, también lo está $*0$ . $(4)$ es $*1$ porque sólo puedes moverte a $*0$ . Desde $(5)$ sólo puedes moverte a $*1$ Así que es $*0$ y perder. Una sola pila par es ganadora, ya que puedes pasar a dos pilas de la mitad de tamaño, y luego reflejar el juego de tu oponente, por lo que es $*0$ . Una sola pila de Impares está perdiendo y es $*1$ .

Afirmo que como primer jugador puedo ganar cualquier juego de la forma $(a,b)$ con $a\gt 1, b \gt 1$ . La cuestión es que una entrada de $0$ en una secuencia equivale a una entrada de $1$ ya que ninguno de los dos puede dividirse y ninguno puede proporcionar la entrada correspondiente. Me moveré a cualquiera de los dos $(a,1)+(0,b-1)$ o a $(a-1,1)+(1,b-1)$ , lo que hace que los números grandes tengan la misma paridad. Entonces, o bien dejo $*0+*0$ o $*1+*1$ , ambos de los cuales son $*0$ y perdiendo para mi oponente.

Creo que se puede hacer un argumento similar para secuencias más largas, pero no lo he desarrollado. Se puede eliminar una de las entradas de la secuencia dejando $0$ o $1$ en ese lugar en una de las secuencias de las hijas y uno de ellos ganará.

Answer 2

Por su pregunta, parece que sólo le interesa el caso de $270000$ . Una jugada ganadora en $270000=2^{4}\times3^{3}\times5^{4}$ es para $A$ para dividirlo en $1350,200$ $=\left(2^{1}\times3^{3}\times5^{2}\right),\left(2^{3}\times3^{0}\times5^{2}\right)$ . Después de eso, cualquier división $B$ hace en uno de esos factores se puede reflejar (dividiendo una potencia de $3$ en lugar de $2$ o viceversa) en el otro, y los futuros movimientos de $B$ también se puede reflejar (el subfactor de $2$ en $1350$ no afecta a nada ya que nunca se puede dividir).

Por ejemplo, si $B$ se mueve en el $200$ componente a $\left(2^{1}\times3^{0}\times5^{0}\right),\left(2^{2}\times3^{0}\times5^{2}\right)$ entonces $A$ puede moverse en el $1350$ componente a $\left(2^{1}\times3^{1}\times5^{0}\right),\left(2^{0}\times3^{2}\times5^{2}\right)$ . Desde $A$ siempre puede reflejar un movimiento de $B$ , $A$ no se quedará en una posición sin movimiento.

Hay otros movimientos ganadores para $A$ como $27000,10$ y $7500,36$ pero es más difícil demostrar que están ganando, ya que ya no hay una estrategia de reflejo directa a seguir.

Si preguntabas por el caso general de un número inicial arbitrario, la cosa se complica un poco (y por favor, acláralo en tu pregunta). Ross Millikan 's respuesta contiene una estrategia para que el primer jugador gane cuando pueda en el caso de uno y dos primos, pero esto no se generaliza bien. En particular, $27000=2^{3}\times3^{3}\times5^{3}$ es una posición perdedora (aunque esto no es obvio). Puede ser esencialmente la única posición perdedora no trivial, pero aún no lo he demostrado. (He estado trabajando en escribir mis resultados en el caso general, pero serán varias páginas y no estoy seguro de que una respuesta de MSE sea el mejor lugar).