0
$\begingroup$

I'm asking that question because I still cannot figure out the solution after hours of thinking.

You are given two towers where first has exactly n stones and second has exactly m stones. You are also given a number k. During each round you can perform one of the actions listed below:

  • take exactly k stones from the first tower,
  • take exactly k stones from the second tower,
  • take exactly k stones from both towers.

There are two players: A and B. Player A starts. The winner is the player who has performed last possible action. How to determine after given n, m, k numbers who has winning strategy (who will win independently from opponent moves).

$\endgroup$
3
  • $\begingroup$ @MohammadZuhairKhan the link you attached is for problem where you should take k stones at turn, but there's no such requirement at all there to take that amount at every turn $\endgroup$ May 12 '19 at 11:24
  • $\begingroup$ My bad, I should have read it better. en.wikipedia.org/wiki/Wythoff%27s_game may help you. $\endgroup$ May 12 '19 at 11:26
  • $\begingroup$ No problem. Thanks for help. $\endgroup$ May 12 '19 at 11:29
0
$\begingroup$

You can divide through by $k$, equvalently making $k=1$.
Let $m=xk+a, n=yk+b$, with both $a$ and $b$ between $0$ and $ k-1$. Then the $a$ and $b$ stones left over play no part in the game. Every round, you reduce either $x$, $y$ or both by $1$.
So let $k=1$. Which positions with $y=0$ are wins, and which are losses ? If $y=1$, can you put the position into a lost position for your opponent ? So which positions are wins when $y=1$? Then do $y=2$, and so on.

$\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.