0
$\begingroup$

Let's say we have a game that is played with two piles containing $x$ and $y$ logs, respectively. For practical purposes, $x,y\in\mathbb{N}$. The objective of the game is to remove that last log. Player 1 goes first and Player 2, second. During their turn, a player can remove as many logs from only one pile as they want. For example, Player 1 could remove all logs from the $x$ pile in their turn (they would not want to do that though since they would lose to Player 2 who would simply remove all logs from $y$).

Who should win the game dependent on $x$ and $y$? Interestingly, this problem is found under the 'induction' section of our text.

$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

HINT: Who should win if $x=y$, and how? Once you’ve answered that correctly, you can easily discover what should happen when $x\ne y$.

$\endgroup$
2
  • $\begingroup$ My thought is that Player 2 can always win since he can always make the piles equal and force Player 1 to eventually take a pile. Still, I'm not sure how to prove this. Thank you for your help so far though. $\endgroup$
    – user322548
    Sep 28, 2016 at 20:46
  • 1
    $\begingroup$ @Ethan: Your idea is correct. Suppose that Player $2$ always takes the same number as Player $1$, but from the other pile. Show that if the piles are equal in size when it’s Player $1$’s turn, then they will again be equal in size but smaller after each player has made one move. Then use the fact that a strictly decreasing sequence of non-negative integers must terminate. $\endgroup$
    – Brian M. Scott
    Sep 28, 2016 at 20:52
0
$\begingroup$

As Brian mentioned, first consider the case in which $x=y$.

In this case the second player is guaranteed a win. If the first player removes $n$ logs from one pile, the second player removes $n$ logs from the other pile. This way the second player is always guaranteed a move. After the second player's move the piles will have the same number of logs in them so this move always works.

If $x\ne y$ the first player always wins. On his first move, he will remove logs from one pile so the piles have the same number of logs. Then he can proceed as the second player in the $x=y$ strategy above.

$\endgroup$

You must log in to answer this question.