🔢 mathematics

The Nim-Sum of a Random Integer Partition

Este artículo determina el comportamiento asintótico de primer orden de la proporción de posiciones perdedoras en particiones enteras de $N$ . La proporción tiende a cero en la escala $1/(\sqrt{N}\log N)$ , pero tras su normalización por su escala natural, no converge; en su lugar, exhibe un patrón de sierra diádico con una transición de paridad de Poisson cerca de los límites diádicos.

Autores originales: Daewon Kim

Publicado 2026-08-28✓ Author reviewed ⓘ

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Daewon Kim

Artículo original bajo licencia CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina un juego que se juega con montones de piedras, donde dos jugadores se turnan para quitar cualquier número de piedras de un solo montón. El objetivo es ser el último en mover, o, por el contrario, forzar al oponente a una posición en la que no tenga un movimiento ganador. Este es el juego de Nim, un clásico rompecabezas de estrategia que ha sido estudiado durante más de un siglo. El secreto para ganar no reside en contar el número total de piedras, sino en una forma específica de combinar los tamaños de los montones utilizando una regla que mezcla la suma y la resta de una manera binaria. Si esta combinación resulta en cero, el jugador cuyo turno es mover está destinado a perder, asumiendo que su oponente juega perfectamente. Durante décadas, los matemáticos han sabido cómo identificar estas posiciones de pérdida para cualquier disposición específica de montones. Pero una pregunta más profunda y elusiva permanecía: si simplemente reúnes un número fijo de piedras y las divides en montones al azar, ¿con qué frecuencia resultará esa disposición aleatoria siendo una de pérdida?

Esta pregunta se sitúa en la intersección entre la teoría de juegos y el estudio de las particiones de enteros, que es el campo matemático que se ocupa de cómo un número puede descomponerse en números enteros más pequeños. Si bien las reglas para ganar un solo juego son precisas y deterministas, el comportamiento de estos juegos cuando la posición inicial se elige al azar es sorprendentemente complejo. Una pregunta natural es si la frecuencia de estas posiciones de pérdida se asienta en un patrón asintótico simple a medida que el número total de piedras crece. Sin embargo, el nuevo trabajo de Daewon Kim, de la Universidad de Hawái en Mānoa, revela que la respuesta es mucho más intrincada que un simple asentamiento estable. A medida que el número de piedras aumenta, la probabilidad bruta de encontrar una posición de pérdida disminuye y tiende hacia cero, lo que significa que estas posiciones se vuelven cada vez más raras. No obstante, si ajustamos esa probabilidad para compensar su disminución natural, la densidad normalizada no se estabiliza en un valor constante. En su lugar, oscila en un patrón dentado y repetitivo que nunca se detiene, sin importar cuán grande sea el número de piedras.

La investigación de Kim se centra en el caso específico en el que el número total de piedras es par, ya que las reglas del juego hacen imposible que un total impar forme una posición de pérdida. Al realizar cálculos exactos, el estudio determina cómo se comporta la densidad de una posición de pérdida a medida que el número total de piedras aumenta. Los hallazgos muestran que esta densidad normalizada no se aproxima a un único valor constante. En su lugar, fluctúa en un patrón de sierra que se repite cada vez que la escala natural asociada al tamaño del problema cruza una potencia de dos. Si graficaras la densidad frente al tamaño del montón, verías una línea que asciende constantemente desde un punto bajo hasta un punto alto, luego cae bruscamente de nuevo, solo para empezar a ascender otra vez. Este ciclo se repite indefinidamente, lo que significa que la densidad normalizada puede estar en cualquier lugar entre uno y dos veces un valor base específico, dependiendo enteramente de dónde te encuentres en este ciclo.

El mecanismo que impulsa este comportamiento tiene sus raíces en la naturaleza binaria de la regla de victoria del juego. Cuando un número grande se descompone en partes más pequeñas, las partes más pequeñas actúan como una fuente de aleatoriedad que desordena los bits inferiores de los números binarios, haciendo que parezcan uniformes e impredecibles. Las partes más grandes son tan raras que rara vez influyen en el resultado. Sin embargo, existe un rango medio específico de tamaños de partes que actúa como un cuello de botella crítico. En este rango, las partes son lo suficientemente grandes como para ser significativas, pero no tanto como para desaparecer. El número de partes que caen en este rango específico determina el resultado. Debido a que este rango cambia a medida que el número total de piedras crece, el equilibrio del juego se inclina de un lado a otro. Cuando la escala natural está justo por debajo de una potencia de dos, el equilibrio se inclina hacia un lado; cuando cruza ese umbral, el equilibrio se invierte, haciendo que la densidad salte.

Para entender esto, uno podría comparar el proceso con un reloj que se reinicia cada vez que alcanza cierta hora, pero cuyas manecillas se mueven a una velocidad que cambia con el tamaño del propio reloj. A medida que el número total de piedras aumenta, el rango crítico de los tamaños de las partes se desplaza hacia arriba. La densidad de una posición de pérdida depende de la paridad de las partes en este rango crítico, la cual actúa como el motor principal de la oscilación. Debido a que la distribución de las partes está gobernada por una ley que se asemeja a una distribución de Poisson, la posibilidad de tener un número par o impar de partes en este rango oscila. Esta oscilación crea el patrón de sierra. La investigación confirma que, a medida que el número total de piedras crece, la densidad normalizada no converge a un solo número. En su lugar, el conjunto de todos los valores posibles a los que se aproxima llena todo el intervalo entre uno y dos veces un factor de escala específico.

El estudio también se extiende más allá de las posiciones de pérdida. Muestra que este mismo comportamiento oscilatorio se aplica a cualquier objetivo fijo específico, no solo al resultado cero. Para cada nim-sum objetivo fijo, la densidad tiene el mismo decaimiento de primer orden y, tras la misma normalización, sigue el mismo perfil de sierra diádica. Esto sugiere que la estructura binaria del juego deja una firma permanente en la distribución aleatoria de los montones, una firma que se niega a ser suavizada por la magnitud de los números involucrados.

Para verificar estas predicciones teóricas, el autor realizó cálculos exactos para cada posible disposición de piedras hasta un total de veinte mil. Esto requirió un enfoque computacional sofisticado que trató el problema como un enorme ejercicio de conteo, utilizando algoritmos especializados para manejar las combinaciones posibles sin necesidad de enumerar cada partición individualmente. Los resultados de estos cálculos coincidieron con las predicciones teóricas con una precisión notable, confirmando que el patrón de sierra es real y no un artefacto del modelo matemático. Los datos mostraron que la densidad sube y baja exactamente como predijo la teoría, con las transiciones bruscas ocurriendo en los momentos precisos en que la escala natural cruza una potencia de dos.

La investigación también profundiza en la naturaleza de la transición entre estos picos y valles. Aunque el gráfico parece tener saltos bruscos y discontinuos, el análisis de tamaño finito indica que el salto aparente no es realmente instantáneo, sino que se suaviza en una ventana cada vez más estrecha mediante un cambio gradual gobernado por si el número de partes en el rango crítico es par o impar. A medida que el número total de piedras aumenta, la ventana en la que ocurre este suavizado se vuelve más estrecha, haciendo que los saltos parezcan más y más agudos a la vista, aunque sigan siendo matemáticamente continuos. Este fenómeno explica por qué el patrón parece tan dentado en los datos, a pesar de que la matemática subyacente es suave.

En última instancia, este trabajo proporciona una descripción completa de cómo se distribuyen las posiciones de pérdida en el juego de Nim cuando la configuración inicial se elige al azar. Resuelve una pregunta de larga data sobre la frecuencia de estas posiciones, mostrando que no siguen una tendencia simple y constante. En su lugar, están gobernadas por una compleja interacción entre el tamaño de los montones y la estructura binaria del juego. Los hallazgos resaltan un principio más amplio en las matemáticas: incluso en sistemas que parecen aleatorios y suaves, las estructuras aritméticas profundas pueden crear patrones agudos y persistentes que resisten el promedio. La naturaleza binaria del juego asegura que un bloque específico de información permanezca visible e influyente, sin importar cuán grande sea el sistema, creando un ritmo que se repite para siempre a medida que los números crecen.

Resumen Técnico: La Suma de Nim de una Partición de Enteros Aleatoria

Planteamiento del Problema
El artículo investiga las propiedades enumerativas de las posiciones ordinarias de Nim con un número total de fichas fijo, $N$ . En el juego de Nim, una posición se define por un multiconjunto de tamaños de montones. Según el teorema de Bouton, una posición es perdedora si y solo si la suma XOR (O exclusivo bit a bit) de los tamaños de los montones es cero. Cuando se ignora el orden de los montones, estas posiciones corresponden a particiones de enteros de $N$ .

El problema central es determinar el comportamiento asintótico de la razón $a_N / p(N)$ , donde $p(N)$ es el número total de particiones de enteros de $N$ , y $a_N$ es el número de tales particiones donde la suma XOR de las partes es cero. Aunque la restricción de paridad es inmediata ( $a_N = 0$ para $N$ impar porque la suma y la XOR comparten el mismo bit menos significativo), la distribución de las posiciones perdedoras para $N$ par presenta un comportamiento complejo: para $N$ par la densidad bruta tiende a cero, mientras que la densidad apropiadamente normalizada exhibe un comportamiento oscilatorio no convergente que las asíntotas estándar de las particiones no logran capturar.

Metodología
El autor emplea un enfoque multifacético que combina la descomposición combinatoria, el modelado probabilístico y la teoría analítica de números:

Descomposición Combinatoria: El artículo descompone una partición $\lambda$ en dos componentes basados en las multiplicidades de sus partes. Si una parte $j$ aparece $c_j$ veces, se escribe como $c_j = 2r_j + \varepsilon_j$ donde $\varepsilon_j \in \{0, 1\}$ . Las copias pares ( $2r_j$ ) se cancelan en la suma XOR, dejando solo el "núcleo impar" (partes con $\varepsilon_j=1$ ). Esto reduce el problema al análisis de la suma XOR de una partición de partes distintas.
Muestreo de Boltzmann: Para explotar la independencia, el estudio se desplaza al modelo de Boltzmann donde el tamaño total es aleatorio. En este modelo, los indicadores para la inclusión de partes distintas son variables de Bernoulli independientes. La probabilidad de una suma XOR cero se analiza particionando los enteros en tres rangos diádicos respecto a una escala crítica $J$ $J$ :
- Bloque Inferior ( $[1, J)$ ): Estas partes pequeñas aleatorizan los bits binarios inferiores, creando una distribución casi uniforme sobre los bits bajos.
- Bloque Crítico ( $[J, 2J)$ ): Este rango determina la probabilidad de primer orden. Cada entero en $[J, 2J)$ tiene el mismo bit principal $J$ ; ese bit principal de la XOR del bloque es cero si y solo si el número de partes seleccionadas en este rango es par, y condicionado a esto, el bloque inferior debe coincidir con el residuo de los bits inferiores restantes.
- Bloque Superior ( $[2J, \infty)$ ): Estas partes grandes son escasas y contribuyen de manera insignificante al término de primer orden.
Jerarquía Diádica y Análisis de Walsh: El autor utiliza el análisis de Walsh (ortogonalidad de caracteres sobre $\mathbb{F}_2$ ) para derivar fórmulas finitas exactas y para refinar la aproximación. Se construye una jerarquía de fórmulas reteniendo más dígitos binarios superiores, lo que permite que la jerarquía diádica refine la aproximación de Boltzmann hasta un orden algebraico arbitrario.
Análisis de Punto de Silla: Para transferir los resultados del modelo de Boltzmann (tamaño aleatorio) de vuelta a las particiones de tamaño fijo, el artículo utiliza métodos de punto de silla sobre las funciones generatrices. Identifica dos sillas iguales (cerca de $q = e^{-t_N}$ y $q = -e^{-t_N}$ ) debido a la paridad de la función generatriz para las posiciones perdedoras. El traslado a particiones de tamaño fijo se establece solo en primer orden.
Computación Exacta: Se implementa un algoritmo exacto basado en la fórmula de Walsh y el Teorema del Resto Chino (CRT) para computar $a_N$ hasta $N=20,000$ . Esto sirve para verificar las fórmulas asintóticas y analizar las correcciones de tamaño finito.

Resultados Clave
El artículo establece el comportamiento asintótico de primer orden de la densidad de las posiciones perdedoras. Sea $\tau_N = \pi/\sqrt{6N}$ y $B_N = \log(1/\tau_N)/\tau_N$ . Sea $J_N$ la potencia de dos más cercana a $B_N$ en distancia multiplicativa, y defina $\Lambda_N = e^{-\tau_N J_N}/\tau_N$ .

Para $N$ par, la razón viene dada por:
$\frac{a_N}{p(N)} = \frac{1 + e^{-2\Lambda_N} + o(1)}{J_N}$

Los hallazgos clave incluyen:

No Convergencia: La densidad normalizada $B_N \frac{a_N}{p(N)}$ no converge, y su conjunto de límites de subsucesiones es el intervalo completo $[1, 2]$ .
Diente de Sierra Diádico: El comportamiento sigue un patrón de "diente de sierra diádico". A medida que $N$ aumenta, el valor sube de 1 a 2 durante cada fase binaria (mientras $B_N$ cruza potencias de dos) y cae de nuevo a 1 cuando la escala cruza una nueva potencia de dos.
Suavizado de Poisson: La aparente discontinuidad en los límites diádicos es suavizada en una escala decreciente por la ley de paridad de una variable aleatoria de Poisson. Específicamente, si $N$ se acerca a un límite tal que $\tau_N K - \log(1/\tau_N) \to c$ (donde $K$ es una potencia de dos), el límite es $1 + e^{-2e^{-c}}$ .
Suma de Nim General: El resultado no es único para la suma XOR cero. Para cualquier suma de nim objetivo fija $x$ , la densidad de las particiones con suma de nim $x$ sigue el mismo perfil de primer orden según la clase de paridad $N \equiv x \pmod 2$ .
Conteos Exactos: El artículo extiende la secuencia OEIS A048833 hasta el índice 10,000 (tamaño total $N=20,000$ ), proporcionando datos exactos que confirman la escala predicha y la estructura de los errores de tamaño finito.

Significancia y Reivindicaciones
El artículo afirma proporcionar la descripción asintótica completa de primer orden de las posiciones perdedoras de Nim para particiones de enteros no restringidas. Su significancia radica en revelar que una estructura aleatoria "suave" (particiones de enteros) retiene una característica aritmética aguda (paridad binaria) debido a la existencia de un único bloque diádico crítico que permanece visible después de que los bits inferiores se aleatorizan y los bits superiores se vuelven insignificantes.

El trabajo demuestra que la densidad de las posiciones perdedoras es del orden $\Theta(1/(\sqrt{N} \log N))$ pero carece de una constante asintótica única. El autor enfatiza que la jerarquía diádica permite refinamientos de la aproximación de Boltzmann hasta un orden algebraico arbitrario, explicando por qué las correcciones de tamaño finito son significativas incluso cuando el teorema de primer orden es válido. El artículo concluye que la no convergencia es un rasgo estructural del problema, no un fallo de la aproximación, y que la transición entre fases está gobernada por la paridad de una variable de Poisson.

El artículo no pretende resolver el problema general para sumas de nim objetivo crecientes o particiones restringidas, señalándolos como preguntas abiertas naturales. Asimismo, evita afirmar que el análisis de la corrección de tamaño finito constituye un teorema completo de segundo orden, ya que se basa en expansiones formales en lugar de cotas uniformes para derivadas de orden superior.

Más como este