The Nim-Sum of a Random Integer Partition

Imagine a game played with piles of stones, where two players take turns removing any number of stones from a single pile. The goal is to be the last one to move, or conversely, to force your opponent into a position where they have no winning move. This is the game of Nim, a classic puzzle of strategy that has been studied for over a century. The secret to winning lies not in counting the total number of stones, but in a specific way of combining the sizes of the piles using a rule that mixes addition and subtraction in a binary fashion. If this combination results in zero, the player whose turn it is to move is destined to lose, assuming their opponent plays perfectly. For decades, mathematicians have known how to identify these losing positions for any specific arrangement of piles. But a deeper, more elusive question remained: if you simply gather a fixed number of stones and divide them into piles at random, how often will that random arrangement turn out to be a losing one?

This question sits at the intersection of game theory and the study of integer partitions, which is the mathematical field concerned with how a number can be broken down into smaller whole numbers. While the rules for winning a single game are precise and deterministic, the behavior of these games when the starting position is chosen randomly is surprisingly complex. A natural question is whether the frequency of losing positions settles into a simple asymptotic pattern as the total number of stones grows. However, the new work by Daewon Kim from the University of Hawai'i at Mānoa reveals that the answer is far more intricate than a simple settling down. While the actual probability of finding a losing position shrinks toward zero as the number of stones increases, the normalized density of these positions does not settle into a steady average. Instead, once this density is rescaled by its natural baseline, it oscillates in a jagged, repeating pattern that never truly stabilizes, no matter how large the number of stones becomes.

Kim's research focuses on the specific case where the total number of stones is even, as the rules of the game make it impossible for an odd total to ever form a losing position. By using an exact counting method, the study determines precisely how the probability of a losing position behaves as the total number of stones increases. The findings show that the normalized density does not approach a single constant value. Instead, it fluctuates wildly, rising and falling in a sawtooth pattern that repeats every time the natural scale associated with the size crosses a power of two. If you were to graph this normalized density against the size of the pile, you would see a line that climbs steadily from a low point to a high point, then drops sharply back down, only to start climbing again. This cycle repeats indefinitely, meaning the normalized density can be anywhere between one and two times its baseline value, depending entirely on where you are in this cycle.

The mechanism driving this behavior is rooted in the binary nature of the game's winning rule. When a large number is broken down into smaller parts, the smallest parts act like a source of randomness that scrambles the lower bits of the binary numbers, making them appear uniform and unpredictable. The largest parts are so rare that they rarely influence the outcome. However, there is a specific middle range of part sizes that acts as a critical bottleneck. In this range, the parts are large enough to be significant but not so large that they disappear. The parity of the number of parts falling into this specific range is the key driver of the oscillation. Because this range shifts as the total number of stones grows, the balance of the game tips back and forth. When the natural scale is just below a power of two, the balance leans one way; when it crosses that threshold, the balance flips, causing the density to jump.

To understand this, one might compare the process to a clock that resets every time it reaches a certain hour, but the hands move at a speed that changes with the size of the clock itself. As the total number of stones increases, the critical range of part sizes moves upward. The probability of a losing position depends on whether this moving range contains an even or odd number of parts. Because the distribution of parts is governed by a law that resembles a Poisson distribution, a statistical model often used to describe rare events, the chance of having an even number of parts in this critical range oscillates. This oscillation creates the sawtooth pattern. The research confirms that as the total number of stones grows, the normalized density does not converge to a single number. Instead, the set of all possible values it approaches fills the entire interval between one and two times a specific scaling factor.

The study also extends beyond just the losing positions. It shows that this same oscillating behavior applies to any fixed target outcome, not just the zero result. For every fixed target nim-sum, the density has the same first-order decay, and after the same normalization it follows the same dyadic sawtooth profile. This suggests that the binary structure of the game leaves a permanent signature on the random distribution of piles, a signature that refuses to be smoothed out by the sheer size of the numbers involved.

To verify these theoretical predictions, the author performed exact calculations for every possible arrangement of stones up to a total of twenty thousand. This was achieved using a sophisticated counting algorithm that computes the exact count of losing positions for every total size without having to enumerate every individual partition. The results of these calculations matched the theoretical predictions with remarkable precision, confirming that the sawtooth pattern is real and not an artifact of the mathematical model. The data showed that the normalized density rises and falls exactly as the theory predicted, with the sharp transitions occurring at the precise moments when the natural scale crosses a power of two.

The research also examines the nature of the transition between these peaks and valleys. While the graph appears to have sharp, discontinuous jumps, the finite-size analysis diagnoses that these jumps are actually smoothed out over a very small scale. This smoothing is governed by the same statistical laws that describe the parity of random events. As the total number of stones increases, the apparent jump is not truly instantaneous; within a shrinking window, it is smoothed into a gradual shift governed by whether the number of parts in the critical range is even or odd. This phenomenon explains why the pattern looks so jagged in the data, even though the underlying mathematics is smooth.

Ultimately, this work provides a complete description of how losing positions are distributed in the game of Nim when the starting configuration is chosen at random. It resolves a long-standing question about the frequency of these positions, showing that they do not follow a simple, steady trend. Instead, they are governed by a complex interplay between the size of the piles and the binary structure of the game. The findings highlight a broader principle in mathematics: even in systems that appear random and smooth, deep arithmetic structures can create persistent, sharp patterns that resist averaging out. The binary nature of the game ensures that a specific block of information remains visible and influential, no matter how large the system grows, creating a rhythm that repeats forever as the numbers get bigger.