For natural numbers $n_1 \leq n_2 \leq n_3$ we define $\beta(n_1,n_2,n_3)$ recursively to be the smallest natural number which is not among the numbers $\beta(m_1,m_2,m_3)$, where $m_1 \leq n_1 \leq m_2 \leq n_2 \leq m_3 \leq n_3$ and $(m_1,m_2,m_3) \neq (n_1,n_2,n_3)$. Recall that $0$ is a natural number.

Question. What is an explicit formula for $\beta(n_1,n_2,n_3)$?

Notice that $\beta(0,n_2,n_3)=\alpha(n_2,n_3)$, where $\alpha$ has been determined here. That is, $\beta(0,n_2,n_3)=n_2+n_3$ if $n_2 \geq \Delta_{k}:=\frac{k(k+1)}{2}$ with $k:=n_3-n_2$ and otherwise $\beta(0,n_2,n_3) = \Delta_{k}+(n_2 - \Delta_{k} - 1 \bmod k+1)$.

Here are some values of the diagonals $(\beta(i,i+k,i+k+l))_i$ (with fixed $k,l \geq 0$), computed with the help of GAP. An overline indicates a conjectural period.

$( \beta(i,i,i) )_i= (0,\overline{1,2,\dotsc})$

$( \beta(i,i,i+1) )_i = (1,2,3,6,3,4,5,6,\overline{3,3,5,\dotsc})$

$( \beta(i,i,i+2) )_i = (2,5,4,7,5,9,12,15,12,4,9,5,\overline{4,7,5,4,6,5,4,7,5,4,8,5,\dotsc})$

$( \beta(i,i+1,i+1) )_i = (0,1,4,4,6,3,4,5,7,4,9,10,\overline{4,7,7,4,6,6,4,9,6,4,8,8,\dotsc})$

It looks as if every diagonal eventually becomes periodic (which is a common theme in combinatorial game theory), but the numbers before the period are "crazy" (in contrast to $\alpha(n_2,n_3)$, which is just $n_2+n_3$ before the period).


After some experimentation I have found the following formula (with $k:=n_3-n_2$):

$$\beta(n_1,n_2,n_3) = \left\{\begin{array}{ll} n_1 + n_2 + n_3 & n_2 \leq \Delta_{k+n_1} \\ n_1 + n_2 - 1 & \Delta_{k+n_1} < n_2 \leq \Delta_{k+n_1+1} \\ \Delta_{k+n_1} + ((n_2 - \Delta_{k+n_1} - 1) \bmod (k+n_1+1)) & n_2 > \Delta_{k+n_1+1} \end{array}\right.$$

I don't have a proof. Also, the formula is only almost correct. For $n_2 > \Delta_{k+n_1+1}$ the formula seems to be fine, but for $n_2 \leq \Delta_{k+n_1+1}$ there are (for fixed $n_1$) a few exceptions.

For example, the values $\beta(1,1,1)$, $\beta(1,2,2)$, $\beta(1,3,3)$, $\beta(1,1,2)$, $\beta(1,3,4)$ are $1,1,2,2,3$, but the formula predicts $3,2,3,4,8$. Apart from these $5$ values, $\beta(1,-,-)$ seems to fit to the formula. For $\beta(2,-,-)$ there are $13$ exceptions, for $\beta(3,-,-)$ there are $19$ of them. How to correct the formula?

  • $\begingroup$ Do you win if you take the last coin off the table, or if you force your opponent to? $\endgroup$ – DanielV Jun 5 '14 at 9:19
  • $\begingroup$ Normal play rule. It turns out that $(n_1,n_2,n_3)$ is a losing position (i.e. $\beta(n_1,n_2,n_3)=0$) iff $n_1=0$ and $n_2=n_3$. $\endgroup$ – Martin Brandenburg Jun 5 '14 at 9:47
  • $\begingroup$ In fact, 1) $(0,n_2,n_2)$ only moves to $(0,m_2,n_2)$ with $m_2 < n_2$, 2) $(n_1,n_2,n_3)$ with $n_1 \neq 0$ or $n_2 \neq n_3$ has a move to $(0,n_2,n_2)$. $\endgroup$ – Martin Brandenburg Jun 5 '14 at 10:31

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.