Restar un cuadrado (también conocido como tomar un cuadrado ) es un juego de resta matemática para dos jugadores . Lo juegan dos personas con una pila de monedas (u otras fichas) entre ellas. Los jugadores se turnan para sacar las monedas de la pila, siempre quitando un número cuadrado de monedas distinto de cero . El juego generalmente se juega como un juego normal , lo que significa que el jugador que retira 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]
Ejemplo
Un juego de juego normal que comienza con 13 monedas es una ganancia para el primer jugador siempre que comience con una resta de 1:
jugador 1:13 - 1 * 1 = 12
El jugador 2 ahora tiene 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 el jugador 1 posteriormente hace lo mismo:
jugador 2: 2 - 1 * 1 = 1jugador 1: 1 - 1 * 1 = 0 el jugador 2 pierde
Teoría matemática
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: intenta pasar un número "frío" a tu oponente. Esto siempre es posible siempre que se le presente un número "caliente". Se pueden determinar de forma recursiva qué números son "calientes" y cuáles son "fríos" :
1) el número 0 es 'frío', mientras que 1 es 'caliente'2) si todos los números 1 .. N se han clasificado como 'calientes' o 'fríos', entonces 2a) el número N + 1 es 'frío' si solo se pueden alcanzar números 'calientes' restando un cuadrado positivo 2b) el número N + 1 es 'caliente' si al menos se puede llegar a un número 'frío' restando un cuadrado positivo
Con este algoritmo, se obtiene fácilmente una lista de números fríos:
Un algoritmo más rápido de dividir y conquistar puede calcular la misma secuencia de números, hasta cualquier umbral, a tiempo . [4]
Hay infinitos números fríos. Más fuertemente, el número de números fríos hasta cierto umbral debe ser al menos proporcional a la raíz cuadrada de , porque 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 infrecuentes. [3] Esto es válido en particular para los números fríos que terminan en 6. De todos los 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 por un cuadrado, porque si lo hicieran, entonces un movimiento del más grande de los dos al más pequeño sería ganador, contradiciendo la suposición de que ambos son fríos. Por lo tanto, según el teorema de Furstenberg-Sárközy , la densidad natural de los números fríos es cero. Es decir, para cada, y para todo lo suficientemente grande , la fracción de los números hasta que están fríos es menos que . Con más fuerza, para cada existen
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]
Extensiones
El juego restar un cuadrado también se puede jugar con varios números. En cada turno, el jugador que realiza un movimiento primero selecciona uno de los números y luego le resta un cuadrado. Esta "suma de juegos normales" puede analizarse utilizando el teorema de Sprague-Grundy . Este teorema establece que cada posición en el juego restar un cuadrado puede mapearse en un tamaño de pila nim equivalente . El juego óptimo consiste en pasar a una colección de números tal que la suma nim de sus tamaños de pila nim equivalentes sea cero, cuando esto sea posible. El tamaño de pila 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 resta de un cuadrado de valores 0, 1, 2, ... los tamaños de pila nim equivalentes son
- 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4,… (secuencia A014586 en la OEIS ).
En particular, una posición de restar un cuadrado es fría si y solo si su tamaño de pila nim equivalente es cero.
También es posible jugar variantes de este juego usando otros movimientos permitidos además de los números cuadrados. Por ejemplo, Golomb definió un juego análogo basado en la secuencia Moser-de Bruijn , una secuencia que crece a una tasa asintótica similar a los cuadrados, para lo cual es posible determinar más fácilmente el conjunto de posiciones frías y definir un estrategia de movimiento óptima. [3]
También se pueden agregar goles adicionales para los jugadores sin cambiar las condiciones ganadoras. Por ejemplo, al ganador se le puede dar un "puntaje" basado en cuántos movimientos se necesitaron para ganar (el objetivo es obtener el puntaje más bajo posible) y al perdedor se le puede dar el objetivo para obligar al ganador a tomar el mayor tiempo posible para alcanzar victoria. Con este par adicional de goles y una suposición de juego óptimo por parte de ambos jugadores, las puntuaciones para las posiciones iniciales 0, 1, 2, ... son
Juego de misère
Resta un cuadrado 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 misère son los números fríos para el juego normal desplazados en 1:
Misère juega números 'fríos':1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...
Ver también
Referencias
- ^ Silverman, David L. (1971), "61. Resta un cuadrado", Tu movimiento: Rompecabezas de lógica, matemáticas y palabras para entusiastas , Publicaciones de Dover, p. 143, ISBN 9780486267319
- ^ Dunn, Angela (1980), "Resta un cuadrado", Mathematical Bafflers , Dover Publications, p. 102, ISBN 9780486239613
- ^ a b c d Golomb, Solomon W. (1966), "Una investigación matemática de los juegos de" comida para llevar " ", Journal of Combinatorial Theory , 1 : 443–458, doi : 10.1016 / S0021-9800 (66) 80016-9 , MR 0209015.
- ^ a b Eppstein, David (2018), "Evaluación más rápida de juegos de resta", en Ito, Hiro; Leonardi, Stefano; Pagli, Linda ; Prencipe, Giuseppe (eds.), Proc. 9th International Conference on Fun with Algorithms (FUN 2018) , Leibniz International Proceedings in Informatics (LIPIcs), 100 , Dagstuhl, Alemania: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 20: 1–20: 12, doi : 10.4230 / lipics.fun.2018.20
- ^ Bush, David (12 de octubre de 1992), "the uniqueness of 11,356" , sci.math
- ^ Pintz, János ; Steiger, WL; Szemerédi, Endre (1988), "Sobre conjuntos de números naturales cuyo conjunto de diferencias no contiene cuadrados", Revista de la Sociedad Matemática de Londres , Segunda Serie, 37 (2): 219-231, doi : 10.1112 / jlms / s2-37.2. 219 , MR 0928519.