Project Euler Problem 899
Two players play a game with two piles of stones.
Solution
Answer: 10784223938983273
Let $P(a,b)$ denote that the position with piles $(a,b)$ is losing for the player to move.
Assume $a\le b$.
A move chooses some $j$ with $1\le j\le a$, leaving
$$(a,b)\to (j,b-j).$$
(Indeed, if we remove $a-j$ stones from the smaller pile and $j$ from the larger pile, the total removed is $a$.)
Key characterization of losing positions
By induction on $a+b$, one finds:
$$P(a,b)\iff a<\operatorname{lowbit}(b+1),$$
where
$$\operatorname{lowbit}(n)=2^{v_2(n)}$$
is the largest power of $2$ dividing $n$.
Examples:
- $b=7$: $\operatorname{lowbit}(8)=8$, so every $1\le a\le7$ is losing.
- $b=11$: $\operatorname{lowbit}(12)=4$, so exactly $a=1,2,3$ are losing.
This matches the sample $L(7)=21$.
Counting losing positions
Fix the larger pile $b$, and let
$$t=\operatorname{lowbit}(b+1).$$
Then the losing positions with larger pile $b$ are exactly
$$a=1,2,\dots,t-1.$$
So:
- if $t=b+1$ (i.e. $b+1$ is a power of $2$), the diagonal pair $(b,b)$ occurs once;
- otherwise every pair contributes twice by symmetry.
Hence the contribution for fixed $b$ is
$$2(t-1)-[b+1\text{ is a power of }2].$$
Therefore
$$L(n) = \sum_{b=1}^n \left(2(\operatorname{lowbit}(b+1)-1)-[b+1\text{ power of }2]\right).$$
Let
$$F(N)=\sum_{k=1}^N \operatorname{lowbit}(k).$$
Then
$$L(n)=2(F(n+1)-1-n)-\lfloor \log_2(n+1)\rfloor .$$
Computing $F(N)$
For each power $2^m$, exactly every $2^m$-th integer contributes at least $2^m$, so
$$F(N)=\sum_{m\ge0} 2^m\left\lfloor \frac{N+2^m}{2^{m+1}}\right\rfloor .$$
Evaluating this for
$$n=7^{17}=232630513987207$$
gives
$$L(7^{17})=10784223938983273.$$
We can verify the formula on the given values:
- $L(7)=21$
- $L(49)=221$
both correct.
Answer: 10784223938983273