3
$\begingroup$

A two-player game is played with two piles of stones, with sizes m,n. On a player's turn, that player can remove any positive number of stones from one pile, or the same positive number of stones from each pile. A player loses when they are unable to take a stone. If 1≤m,n≤30, for how many of the 30×30=900 starting positions does the first player have a winning strategy?

$\endgroup$
2
  • $\begingroup$ I.e., the winner takes the last stones. If there are the same number of stones on both piles, the next player can take all, so the strategy must be to keep them different and none empty (one pile empty means the other player can take it all). $\endgroup$
    – vonbrand
    Mar 23, 2013 at 20:32
  • 3
    $\begingroup$ This is known as Wythoff's game. It has a very interesting theory. $\endgroup$
    – MJD
    Mar 24, 2013 at 13:38

1 Answer 1

2
$\begingroup$

As pointed out by MJD, this game is known as Wythoff's game and has a very interesting theory. As discovered by Wythoff, the losing positions are the pairs $(m_k,n_k)$ and $(n_k,m_k)$ with

$$ n_k=\left\lfloor k\phi\right\rfloor\;,\\ m_k=\left\lfloor k\phi^2\right\rfloor\;, $$

where $k\in\mathbb N$ and $\phi=\frac{1+\sqrt5}2$ is the golden ratio. Solving $k\phi^2\lt31$ for $k$ yields $k\lt31/\phi^2\approx 11.84$, so there are $2\cdot11=22$ losing positions and thus $900-22=878$ winning positions with $1\le m,n\le30$.

$\endgroup$

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.