2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot! I will try to check this pattern. $\endgroup$ – Martin Brandenburg Apr 30 '13 at 20:56
  • $\begingroup$ iow idk = in other words I don't know? $\endgroup$ – Martin Brandenburg May 3 '13 at 16:25
  • $\begingroup$ Yup! I mean that it looks like it might be just barely possible to prove this by induction, but I don't know for sure. And I'm not sure I want to try it that way :-) I tried to think of a way of seeing something useful about the sum of this game and a NIM-game, but nothing so far. $\endgroup$ – Jyrki Lahtonen May 3 '13 at 16:49
  • 1
    $\begingroup$ So you claim that $\alpha(n,m)=n+m$ if $n \leq \Delta_k$, where $k=m-n$, and else $\alpha(n,m)=d+(n-d-1 \bmod k+1)$. I have verified this formula for $n,m \leq 40$. I still cannot prove it. Somehow one has to prove that $\alpha$ defined this way satisfies the recursion $\alpha(n,m) = \mathrm{mex} \{\alpha(n',m'):n' \leq n \leq m' \leq m, (n',m') \neq (n,m)\}$. $\endgroup$ – Martin Brandenburg May 4 '13 at 19:56
  • 1
    $\begingroup$ The induction works. It is just a little bit long. $\endgroup$ – Martin Brandenburg Jun 5 '14 at 8:11

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.