El juego de resta de cuadrados (también conocido como " quitar un cuadrado ") es un juego matemático de resta para dos jugadores . Lo juegan dos personas con una pila de monedas (u otras fichas) entre ellas. Los jugadores se turnan para quitar monedas de la pila, siempre quitando un número de monedas distinto de cero. El juego se juega normalmente como un juego normal , lo que significa que el jugador que quita la última moneda gana. [1] [2] Es un juego imparcial , lo que significa que el conjunto de movimientos disponibles desde cualquier posición no depende de quién sea el turno. Solomon W. Golomb atribuye la invención de este juego a Richard A. Epstein . [3]
Una partida normal que comienza con 13 monedas es una victoria para el primer jugador, siempre que comience con una resta de 1:
Jugador 1: 13 - 1*1 = 12
El jugador 2 tiene ahora tres opciones: restar 1, 4 o 9. En cada uno de estos casos, el jugador 1 puede asegurarse de que en unos pocos movimientos el número 2 pase al jugador 2:
Jugador 2: 12 - 1*1 = 11 Jugador 2: 12 - 2*2 = 8 Jugador 2: 12 - 3*3 = 3Jugador 1: 11 - 3*3 = 2 Jugador 1: 8 - 1*1 = 7 Jugador 1: 3 - 1*1 = 2 Jugador 2: 7 - 1*1 = 6 o: 7 - 2*2 = 3 Jugador 1: 6 - 2*2 = 2 3 - 1*1 = 2
Ahora el jugador 2 tiene que restar 1, y posteriormente el jugador 1 hace lo mismo:
Jugador 2: 2 - 1*1 = 1Jugador 1: 1 - 1*1 = 0 El jugador 2 pierde
En el ejemplo anterior, el número "13" representa una posición ganadora o "caliente", mientras que el número "2" representa una posición perdedora o "fría". Dada una lista de números enteros con cada número entero etiquetado como "caliente" o "frío", la estrategia del juego es simple: tratar de pasarle un número "frío" a su oponente. Esto siempre es posible siempre que se le presente un número "caliente". Qué números son "calientes" y cuáles son "fríos" se puede determinar recursivamente :
Usando este algoritmo, se deriva fácilmente una lista de números fríos:
Un algoritmo de dividir y vencer más rápido puede calcular la misma secuencia de números, hasta cualquier umbral , en el tiempo . [4]
Hay una cantidad infinita de números fríos. Más fuertemente, la cantidad de números fríos hasta cierto umbral debe ser al menos proporcional a la raíz cuadrada de , ya que de lo contrario no habría suficientes para proporcionar movimientos ganadores de todos los números calientes. [3] Los números fríos tienden a terminar en 0, 2, 4, 5, 7 o 9. Los valores fríos que terminan con otros dígitos son bastante poco comunes. [3] Esto se aplica en particular a los números fríos que terminan en 6. De todos los más de 180.000 números fríos menores de 40 millones, solo uno termina en 6: 11.356. [5]
No hay dos números fríos que puedan diferir en un cuadrado, porque si lo hicieran, un movimiento del mayor de los dos al menor sería ganador, contradiciendo la suposición de que ambos son fríos. Por lo tanto, por el teorema de Furstenberg-Sárközy , la densidad natural de los números fríos es cero. Es decir, para cada , y para todos los suficientemente grandes , la fracción de los números hasta que son fríos es menor que . Más fuertemente, para cada hay
números fríos hasta . [6] La tasa de crecimiento exacta de los números fríos sigue siendo desconocida, pero experimentalmente el número de posiciones frías hasta cualquier umbral dado parece ser aproximadamente . [4]
El juego de restar un cuadrado también se puede jugar con varios números. En cada turno, el jugador que va a hacer un movimiento primero selecciona uno de los números y luego le resta un cuadrado. Esta "suma de juegos normales" se puede analizar utilizando el teorema de Sprague-Grundy . Este teorema establece que cada posición en el juego de restar un cuadrado se puede asignar a un tamaño de montón nim equivalente . El juego óptimo consiste en moverse a una colección de números tales que la suma nim de sus tamaños de montón nim equivalentes sea cero, cuando esto sea posible. El tamaño de montón nim equivalente de una posición se puede calcular como el valor mínimo excluido de los tamaños equivalentes de las posiciones que se pueden alcanzar con un solo movimiento. Para posiciones de restar un cuadrado de valores 0, 1, 2, ... los tamaños de montón nim equivalentes son
En particular, una posición de restar un cuadrado es fría si y solo si su tamaño de montón nim equivalente es cero.
También es posible jugar variantes de este juego utilizando otros movimientos permitidos que los números cuadrados. Por ejemplo, Golomb definió un juego análogo basado en la secuencia de Moser–de Bruijn , una secuencia que crece a una tasa asintótica similar a la de los cuadrados, para la cual es posible determinar más fácilmente el conjunto de posiciones frías y definir una estrategia de movimiento óptima fácilmente calculada. [3]
También se pueden añadir objetivos adicionales para los jugadores sin cambiar las condiciones de victoria. Por ejemplo, se puede dar al ganador un "puntaje" basado en la cantidad de movimientos necesarios para ganar (el objetivo es obtener el puntaje más bajo posible) y al perdedor el objetivo de obligar al ganador a tardar el mayor tiempo posible en alcanzar la victoria. Con este par de objetivos adicionales y suponiendo que ambos jugadores juegan de manera óptima, los puntajes para las posiciones iniciales 0, 1, 2, ... son
El juego de restar cuadrados también se puede jugar como un juego de misère , en el que el jugador que haga la última resta pierde. El algoritmo recursivo para determinar los números "calientes" y "fríos" para el juego de misère es el mismo que para el juego normal, excepto que para el juego de misère el número 1 es "frío" mientras que el 2 es "caliente". De ello se deduce que los números fríos para la variante de misère son los números fríos para el juego normal desplazados en 1:
Misère toca números 'fríos':1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...
