---

Problem 665

---

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)$.

---

等比例取石子游戏

两名玩家正在玩一个取石子游戏，这个游戏需要两堆石子，两名玩家交替行动。

在每一回合，轮到行动的玩家选择一个正整数$n$，然后进行以下操作之一：

• 从一个堆中移除$n$个石子；
• 从两个堆中各移除$n$个石子；
• 从一个堆中移除$n$个石子，并从另一个堆中移除$2n$个石子。

最终，移除最后一个石子的玩家获胜。

我们用$(n,m)$表示两堆分别还剩$n$个和$m$个石子的状态。注意$(n,m)$和$(m,n)$被视为相同的状态。

比如说，如果当前状态是$(2,6)$，那么即将行动的玩家可以达成的状态包括：
$(0,2)$, $(0,4)$, $(0,5)$, $(0,6)$, $(1,2)$, $(1,4)$, $(1,5)$, $(1,6)$, $(2,2)$, $(2,3)$, $(2,4)$, $(2,5)$

如果即将行动的玩家不能确保获胜，则称当前状态为必败态。例如，$(1,3)$，$(2,6)$和$(4,5)$就都是必败态。

对于所有满足$n\le m$和$n+m\le M$的必败态$(n,m)$，记它们的$n+m$的总和为$f(M)$。例如，$f(10)=21$，对应的所有必败态即为$(1,3)$，$(2,6)$和$(4,5)$。

已知$f(100)=1164$，$f(1000)=117002$。

求$f({10}^7)$。

---