Proportionate Nim

Two players play a game with two piles of stones, alternating turns.
On each turn, the corresponding player chooses a positive integer $n$ and does one of the following:
removes $n$ stones from one pile;
removes $n$ stones from both piles; or
removes $n$ stones from one pile and $2n$ stones from the other pile.
The player who removes the last stone wins.
We denote by $(n,m)$ the position in which the piles have $n$ and $m$ stones remaining. Note that $(n,m)$ is considered to be the same position as $(m,n)$.
Then, for example, if the position is $(2,6)$, the next player may reach the following positions:
$(0,2)$, $(0,4)$, $(0,5)$, $(0,6)$, $(1,2)$, $(1,4)$, $(1,5)$, $(1,6)$, $(2,2)$, $(2,3)$, $(2,4)$, $(2,5)$
A position is a losing position if the player to move next cannot force a win. For example, $(1,3)$, $(2,6)$, $(4,5)$ are the first few losing positions.
Let $f(M)$ be the sum of $n+m$ for all losing positions $(n,m)$ with $n\le m$ and $n+m \le M$. For example, $f(10) = 21$, by considering the losing positions $(1,3)$, $(2,6)$, $(4,5)$.
You are given that $f(100) = 1164$ and $f(1000) = 117002$.
Find $f(10^7)$.

Truth be told, finding the sum of $n+m$ for all losing positions $(n,m)$ based on the rules given, especially up to $10^7$, is not something you could practically do by hand. You would want to use a computer program to generate and check these kinds of positions at scale.

However, even for a computer, it’s not as simple as generating all the positions and checking them one by one. To solve this efficiently, we need to understand the pattern and properties of the game. For instance, we know from the game’s definition that if $(n,m)$ is a losing position, then a winning position can be formed by removing $n$ stones from one pile, or $n$ stones from both piles, or $n$ stones from one pile and $2n$ stones from the other pile.

The best way to go about this task would involve dynamic programming, which essentially means solving the problem in smaller parts, storing the answers to those smaller parts, and using those stored answers to build up to the solution of larger parts.

Since the problem states “if the position is a losing position, the player to move next cannot force a win,” we would start by considering the smallest positions and then gradually build up to larger ones.

To find $f(10^7)$, a suggested Python program would feature a defined function `f(M)` that uses dynamic programming, recursively going through smaller `n` and `m` values to find all losing positions, summing `n+m`, and caching the values of `f(M)` for future use. The critical strategy is to enumerate all possible operations (removing `n` stones from one pile, both piles, or `n` and `2n` stones), then compute `n’ = n – dn`, `m’ = m – dm` for all feasible `(dn, dm)`, and finally check if `(n’, m’)` is a losing position.

That being said, this problem is rather challenging and goes beyond the usual scope of high school mathematics. Completing the task would require a specialized computer algorithm and deep understanding of number theory. Likely, this problem is a part of a programming challenge or a complex gaming theory study.

More Answers: