0
$\begingroup$

If I want to solve a game of nim with 3 piles containing (x, 2x, 3x) respectively

I know that the solution of (winning) iff x^2x^3x != 0

but if x can be in the range from 1 to 2^61 so How many winning states in this range?

I want to solve this problem ... I tried to find a pattern but I think there is no pattern for that

|cite|improve this question
$\endgroup$
  • $\begingroup$ Try understanding first when $a\oplus b = a+b$. $\endgroup$ – Yuval Filmus Nov 28 '17 at 19:29
  • $\begingroup$ Because a xor b xor c ≠ 0 iff a xor b ≠ c. And x xor 2x xor 3x ≠ 0 iff x xor 2x ≠ 3x. $\endgroup$ – gnasher729 Dec 28 '17 at 23:05
2
$\begingroup$

Let $a=a_{n-1} \cdots a_0$ and $b=b_{n-1} \cdots b_0$ be two positive integers with given binary expansion. Since $z+w = 2(z \land w) + (z \oplus w)$, we have $$ a + b = a \oplus b + 2(a \land b), $$ where $a \oplus b$ and $a \land b$ are bitwise XOR and AND. In particular, $a + b = a \oplus b$ iff $a \land b = 0$.

Consider now the equation $x \oplus 2x \oplus 3x = 0$. We can rewrite it as $x \oplus 2x = 3x = x + 2x$. Above we have seen that this is equivalent to $x \land 2x = 0$. If $x = x_{n-1} \ldots x_0$ then $$ x \land 2x = 0 (x_{n-1} \land x_{n-2}) \ldots (x_1 \land x_0) 0. $$ Thus $x \oplus 2x \oplus 3x = 0$ if the binary expansion of $x$ doesn't contain two adjacent 1s.

It remains to count how many binary strings of length $n$ (in your case, $n = 61$) satisfy this condition. It is a standard exercise to show that the answer is the Fibonacci number $F_{n+2}$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.