After so much time, I’ve finally reach the top ranking 2 in my country in Project Euler. I still have a really long run to achieve the top 1, but the most important thing is the path.
The solution is straightforward, but it’s hard to explain just in text, anyway, I’ll try.
Statement
Nim is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.
We’ll consider the three-heap normal-play version of Nim, which works as follows:
- At the start of the game there are three heaps of stones.
- On each player’s turn, the player may remove any positive number of stones from any single heap.
- The first player unable to move (because no stones remain) loses.
If $(n_{1}, n_{2}, n_{3})$ indicates a Nim position consisting of heaps of size $n_{1}$, $n_{2}$, and $n_{3}$, then there is a simple function, which you may look up or attempt to deduce for yourself, $X(n_{1}, n_{2}, n_{3})$ that returns:
- zero if, with perfect strategy, the player about to move will eventually lose; or
- non-zero if, with perfect strategy, the player about to move will eventually win.
For example $X(1, 2, 3) = 0$ because, no matter what the current player does, the opponent can respond with a move that leaves two heaps of equal size, at which point every move by the current player can be mirrored by the opponent until no stones remain; so the current player loses. To illustrate:
- current player moves to $(1,2,1)$
- opponent moves to $(1,0,1)$
- current player moves to $(0,0,1)$
- opponent moves to $(0,0,0)$, and so wins.
For how many positive integers $n \leq 2^{30}$ does $X(n, 2n, 3n) = 0$?
Solution
If you know a bit of game theory, then you probably know Nim Game. Long story short, you can always win a Nim game if the xor of the number of piles is 0.
So, the problem is just basically to find which numbers $n$ are that $n\land (2n) \land (3n) = 0$.
Let’s supposse that the number $n$ has an arbitrary number of 0’s in the right.
\begin{aligned} n &= \ldots a_{2}& a_{3}& 1& 0& &\ldots 000\cr 2n &= \ldots a_{3}& 1& 0& 0& &\ldots 000\cr 3n &= \ldots ((a_{2}+a_{3}+(a_{3}+1)/2)\%2)& ((a_{3}+1)\%2)& 1& 0& &\ldots 000\cr X(n, 2n, 3n) &= \ldots (a_{2}\land a_{3}\land (a_{2}+a_{3}+(a_{3}+1)/2)\%2)& (a_{3}\land 1 \land (a_{3}+1)\%2)& 0& 0& &\ldots 000 \end{aligned}
The value of $S = a_{2}\land a_{3}\land (a_{2}+a_{3}+(a_{3}+1)/2)\%2$ should be 0.
If $a_{3} = 1$, then $S = a_{2}\land 1\land (2+a_{2})\%2 = a_{2}\land 1 \land a_{2} = 1 \neq 0$.
If $a_{3} = 0$, then $S = a_{2}\land 0 \land (a_{2})\%2 = a_{2}\land 0 \land a_{2} = 0$. It means that, the only possible solution is to set $a_{3} = 0$, and the value of $a_{2}$ could be $1$ or $0$. If we set $a_{2} = 1$, then we can apply this same logic again and check that $a_{1} = 0$, and so on.
Finally, the conclusion is that, $n$ is a number that doesn’t have two consecutive $1$’s in its binary representation.
The easiest way to generate all numbers with this representation is just making a recursion.
\begin{aligned} f(k) = f(2k) + \Big\vert k\vert 2 \Big\vert f(2k+1) \end{aligned}
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1 << 30)
int n;
ll solve(ll current = 0) {
if (current == 0 or current > MAXN)
return 0;
ll ans = 0;
int last_bit = (current & 1);
if (last_bit == 0) {
ans += solve(current * 2 + 1);
}
ans += solve(current * 2);
if (current <= MAXN)
ans++;
return ans;
}
int main() {
int n;
cin >> n;
if (n == -1)
n = MAXN;
n = min(n, MAXN);
ll ans = solve(1);
cout << ans << '\n';
return 0;
}