Exceptional values in a combinatorial game

Question

Consider the following combinatorial game: We have two heaps of sizes $n_1 \leq n_2$ (with $n_1,n_2 \in \mathbb{N}$). A move leaves the sizes $m_1,m_2$, where $0 \leq m_1 \leq n_1 \leq m_2 \leq n_2$, and $m_i \neq n_i$ for at least one $i$. Equivalently, we move some piece on an infinite checker board above the diagonal and the possible moves are as follows:

I have tried to compute the nimber (aka Sprague-Grundy value) of this game, let's call it $\alpha(n_1,n_2)$. Thus, $\alpha(n_1,n_2)$ is the mex of the numbers $\alpha(m_1,m_2)$, where $0 \leq m_1 \leq n_1 \leq m_2 \leq n_2$, and $m_i \neq n_i$ for some $i$. It is easy to show $\alpha(n_1,n_2)=0 \Leftrightarrow n_1=n_2$, these are the losing positions. Some experiments show that we have $\alpha(n_1,n_2)=n_1+n_2$ for large values of $n_2$, depending on $n_1$. The length of the "exceptional" values seems to be increasing. I wonder, is there any pattern here? Can you give an explicit formula?

Also, is this game already known?

Here are the first values (the "exceptional" ones underlined):

$$\begin{array}{cccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ & 0 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ && 0 & \underline{1} & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ &&& 0 & \underline{2} & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ &&&& 0 & \underline{1} & \underline{3} & 11 & 12 & 13 & 14 & 15 \\ &&&&& 0 & \underline{2} & \underline{4} & 13 & 14 & 15 & 16\\ &&&&&& 0 & \underline{1} & \underline{5} & 15 & 16 & 17 \\ &&&&&&& 0 & \underline{2} & \underline{3} & \underline{6} & 18 \end{array}$$

In his answer, Jyrki Lahtonen looks at the diagonals and has found the following formula:

$$\alpha(n,m) := \left\{\begin{array}{ll} n + m & n \leq \Delta_k \\ d + (n-d-1 \bmod k+1) & n > \Delta_k \end{array}\right.$$

Here, $k:=m-n$ and $\Delta_k := \frac{k(k+1)}{2}$. Does someone have an idea how to prove this?

Answer 1

Not a solution, but a conjecture as to what the $\alpha$ function looks like. It is simpler to describe the sequences $\alpha(n,n+k)$ for a fixed $k$. The other parameter $n$ will then range from $0$ to $\infty$. I conjecture that this sequence is the following. I abbreviate $\Delta_k:=k(k+1)/2$.

• It begins by sharing $\Delta_k+1$ values with the function $\beta(n_1,n_2)=n_1+n_2$. In other words $\alpha(n,n+k)=2n+k$, if $0\le n\le \Delta_k$.
• After that beginning it repeats the cycle of $k+1$ consecutive natural numbers starting from $\Delta_{k}$ and ending with $\Delta_{k}+k=\Delta_{k+1}-1.$

So we have (I place a vertical bar after the linearly growing initial fragment):

• $\alpha(n,n+0)_{n\ge0}=0|0,0,0,\ldots,$
• $\alpha(n,n+1)_{n\ge0}=1,3|1,2,1,2,1,2,\ldots,$
• $\alpha(n,n+2)_{n\ge0}=2,4,6,8|3,4,5,3,4,5,\ldots,$
• $\alpha(n,n+3)_{n\ge0}=3,5,7,9,11,13,15|6,7,8,9,6,7,8,9,\ldots$
• $\alpha(n,n+4)_{n\ge0}=4,6,8,10,12,14,16,18,20,22,24|10,11,12,13,14,10,11,12,13,14,\ldots$

Proving this by induction is may be (Edit: IOW, IDK) possible but looks very messy. May be a simpler way of writing this is out there? Anyway, this conjecture would imply the truth of Martin's observations.