3
$\begingroup$

Given the following game, what is the strategy to win?

  • There are 3 heaps with m, n, k stones respectively. m, n, k must all be >1 and can be the same.
  • At each turn, each player can take either 1 from a single tower or 2 stones from 2 different towers (1 from each tower)
  • EDIT: The winner is the person to take the last stone(s). Thus, (0, 1, 1) or (0, 0, 1) are winning positions.

I need to know given a position who is predicted to win and what's the best move to take.

I've been trying to compare this problem with Nim, Substraction Games, Grundy Numbers etc., but the problem is that they are all based on taking an amount larger than 1 from a single tower.

Any help is appreciated. Thanks in advance!

$\endgroup$
0
3
$\begingroup$

Unfortunately, it turns out simply.
Losing positions are where $(m,n,k)$ are either all even or all odd.
It is more complicated if the last stone loses, I don't have a formula for that.

$\endgroup$
3
  • $\begingroup$ This worked, thank you! Would love an explanation how you got there. $\endgroup$
    – Guy Azu
    Aug 17 '19 at 14:55
  • $\begingroup$ I am afraid I just coded up Nicolas' method, and then looked at the results one $k$ at a time. $\endgroup$
    – Empy2
    Aug 17 '19 at 15:13
  • $\begingroup$ Didn't go far enough to see that general formula :-) But the problem is still interesting, because the formula doesn't come simply, you have to experiment to see it. Now I want to find a proof for it :-) $\endgroup$ Aug 17 '19 at 18:16
0
$\begingroup$

My reflections up to now : a position is coded $(p,q,r)$, with $p\le q\le r$.

  • $(0,0,n)$ leads only to $(0,0,n-1)$, so it's a wining position if $n$ is odd, a loosing one if $n$ is even.
  • $(0,1,n)$ leads to $(0,0,n)$, $(0,0,n-1)$ or $(0,1,n-1)$. At least one of this positions is a loosing one, so $(0,1,n)$ is a winning position for all $n\ge1$.
  • $(0,2,n)$ can lead to $(0,1,n)$ or $(0,1,n-1)$, one of which is a loosing position, so $(0,2,n)$ is winning for all $n\ge2$.
  • $(0,3,n)$ leads to $(0,2,n)$ or $(0,2,n-1)$ which are both winning position, or $(0,3,n-1)$. As $(0,3,3)$ is loosing, $(0,3,n)$ is winning if $n$ is even, loosing if $n$ is odd.
  • $(1,1,n)$ can lead to $(0,1,n)$ or $(0,1,n-1)$, one of which is loosing, so $(1,1,n)$ is winning for all $n\ge2$. But $(1,1,1)$ is loosing.

I'll continue until I find a more general result.

Very interesting problem, I'll try it with my classes :-)

$\endgroup$
3
  • 1
    $\begingroup$ How is $(2, 2, 0)$ winning? Both $(2, 1, 0)$ and $(1, 1, 0)$ are winning positions (the winning moves being to go to $(2, 0, 0)$ and $(0, 0, 0)$ respectively). $\endgroup$
    – Unit
    Aug 17 '19 at 13:05
  • $\begingroup$ This was very helpful to try and explore the answer, thanks $\endgroup$
    – Guy Azu
    Aug 17 '19 at 14:56
  • $\begingroup$ @Unit : because I didn't see $(2,1,0)$ is winning... Sorry. $\endgroup$ Aug 17 '19 at 18:15

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.