Let a Nim game be represented by a sequence of positive integers. We call a Nim of size $n$ when the sum of its elements is $n$.

Let $a(n)$ be the number of Nim games of size $2n$ with Nim sum 0. Similarly, let $b(n)$ be the number of Nim games of size $2n$ with Nim sum 2.

I'm trying to prove (or possibly disprove) $$\lim_{n\to\infty}\frac{a(n)}{b(n)}=1.$$

I've calculated the first values with help of a computer; by $n=250$, this fraction is about $1-10^{-50}$, so there's clearly some convergence going on. I haven't been able to prove it, however. I've been trying to establish some sort of "partial bijection" between the sets of Nim games of Nim sum 0 and 2, but that hasn't worked. I've tried using recursion, I've gotten nothing. Any help?

  • $\begingroup$ Intuitively, I am not surprised. Given an position with sum $0$ you can make one with sum $2$ by adding a pile of $2$. Similarly, given one of sum $2$ you can make a pile of sum $0$ by adding a pile of $2$. Yes, each of these increases $n$ by $2$, but for large $n$ this doesn't matter. There are theorems of equilibrium distributions in Markov chains that may apply, but I haven't studied those. I suspect you can prove that for $n$ large enough, the positions of value $k$ have similar cardinality when $k \ll n$ $\endgroup$ Feb 19, 2019 at 5:16
  • 3
    $\begingroup$ @RossMillikan: I think "for large $n$ this doesn't matter" is wrong in this case, though, since the growth of $a(n)$ and $b(n)$ is exponential. For instance, $a(n+2)\geq 2a(n)$ since given a game of size $2n$ you can turn it into a game of size $2n+4$ by adding either $(2,2)$ or $(1,1,1,1)$ to the end. So, your argument shows $a(n)\leq b(n+1)\leq a(n+2)$ but this doesn't give a strong bound on the ratio $a(n)/b(n)$. $\endgroup$ Feb 19, 2019 at 5:29
  • $\begingroup$ @bof Yes, I've fixed that. $\endgroup$ Feb 19, 2019 at 13:49
  • 2
    $\begingroup$ Does order matter when counting Nim positions? That is, is $(2,1,1)$ considered distinct from $(1,2,1)$? $\endgroup$ Feb 19, 2019 at 19:32
  • 1
    $\begingroup$ @MikeEarnest Yes, they're sequences. $\endgroup$ Feb 19, 2019 at 20:43


Your Answer

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

Browse other questions tagged or ask your own question.