# Question about proportion of Nim positions

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?

• 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$ – Ross Millikan Feb 19 at 5:16
• @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)$. – Eric Wofsey Feb 19 at 5:29
• @bof Yes, I've fixed that. – Anonymous Pi Feb 19 at 13:49
• Does order matter when counting Nim positions? That is, is $(2,1,1)$ considered distinct from $(1,2,1)$? – Mike Earnest Feb 19 at 19:32
• @MikeEarnest Yes, they're sequences. – Anonymous Pi Feb 19 at 20:43