5
$\begingroup$

Amy and Beck are playing 'taking the stones game'. There are 18 stones on the table, and the two people take stones in turns. The first move of the starting player can take 1 to 4 stones. For the rest of the game, each player takes a number of stones from 1 up to twice the number of stones his/her opponent just took. The player taking the last stone wins. Amy comes first. If Amy has a winning strategy, how many stones should Amy take? (at the start) If Amy does not have a winning strategy, write '0'.

I tried like copying same moves for Amy and Beck etc. and did a few manual computations to see that it's not possible. An answer key with no solution says that there is no winning strategy as it gives "0" as the answer. Anyone know how to prove it? Is there an invariant or something which I am missing? I have some background in Math Olympiad and a Math related degree so feel free to use any techniques.

$\endgroup$
0

1 Answer 1

Reset to default
7
$\begingroup$

Given that you have Math Olympiad background, I assume that you're familiar with setting up winning positions. You might think that doesn't work here because we don't have exact / clean-cut winning positions on $n$ stones, since gameplay also depends on how many stones the previous player took. That is fine, we simply make the winning positions conditional on how many stones the current player can take, namely $(n, k)$, where $n$ is the number of stones left, and $k$ is how many they can remove. The question asks if $(18, 4)$ is a winning position, and how to play it.

We proceed via the typical recursive Winning Positions analysis. The solution is intentionally left incomplete. I've gotten you started almost till the very end. Can you complete it to 18 stones?

First, some initial observations

  1. Since the game is symmetric in moves, let $X$ denote the player to move, and $Y$ the other player.
  2. Note that each time, X can always take 1 or 2 stones.
    • Wishful thinking that this allows us to figure things out.
    • In particular, if $(n-1,k)$ is always a losing position, or if $(n-2,k)$ is always a losing position, then $(n,k)$ is always a wining position.
  3. If X takes 1 (or 2) stone, then that's very restrictive on Y.
    • This might allows us to figure out some game play, esp to prevent Y from hitting some winning positions that require taking many stones.
    • You will see this come into play with 12 stones, as $(11, \geq 3)$ is a winning position, but $(11, 1), (11,2)$ are losing positions. So from $(12,k)$, we take 1 stone to leave them with $(11, 2)$ which is a losing position.

Now, let's construct the winning positions:

  • If there are 1 stone left, then X wins
  • If there are 2 stones left, then X wins
    • Recall that X can take 2 stones
  • If there are 3 stones left, and X can't take 3+ stones, then X loses
    • If X takes 1/2 stones, then Y is left with 2/1 stone and wins.
  • If there are 4 stones left, then X wins
    • If X takes 1 stone, Y is left with 3 so Y loses
  • If there are 5 stones left, and X can't take 5+ stones, then X loses.
    • If X takes 1 stone, Y has 4 left so Y wins
    • If X takes 2/3/4 stones, Y will take 3/2/1 stone and wins
  • If there are 6 stones left, then X wins
    • X takes 1 stone, leaving 5, so Y loses
  • If there are 7 stones left, then X wins
    • X takes 2 stones, leaving 5. Y loses
  • If there are 8 stones left, and X can't take 8+ stones, then X loses
    • If X takes 1 stone, leaving 7, Y wins
    • If X takes 2 stones, leaving 6, Y wins
    • If X takes 3-7 stones, Y takes the rest.
  • If there are 9 stones left, X wins
    • X takes 1 stone, leaving 8, so Y loses
  • If there are 10 stones left, X wins
    • X takes 2, leaving 8. Y loses
  • If there are 11 stones left, and X can't take 3+ stones, then X loses. Else X wins.
    • If X takes 1/2 stones, then Y has 10/9 stones and Y wins.
    • Else X takes 3 stones, leaving 8 to Y and Y loses.
  • If there are 12 stones left, X wins
    • X takes 1 stone leaving 11. Y can't take 3+ stones hence Y loses
  • If there are 13 stones left, X loses
    • If X takes 1/3/4 stone, leaving 12/10/9, Y wins
    • If X takes 2 stones leaving 11, Y can take 3 and Y wins
    • If X takes 5 or more stones, Y takes the rest and Y wins
    • In particular, if Amy could take 5 stones from 18, then Beck loses.
  • Continue this to show that Amy loses the game as defined.
$\endgroup$
3
  • $\begingroup$ This is a minor nitpick, but none of what you're doing uses Sprague-Grundy (which helps analyze sums of games). It's just applying the simpler Zermelo's theorem about games. $\endgroup$
    – Mark S.
    Commented Mar 1 at 18:15
  • $\begingroup$ @MarkS. Indeed. Edited. $\endgroup$
    – Calvin Lin
    Commented Mar 1 at 18:28
  • $\begingroup$ Hi Calvin, that's a great explanation. Thank you so much ya! $\endgroup$
    – Jonny Boy1
    Commented Mar 2 at 1:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .