4.9 A subtraction game Subtraction games are two-player games in which there is

Question

4.9 A subtraction game Subtraction games are two-player games in which there is a pile of objects, say coins. There are two players, Alice and Bob, who alternate turns subtracting 4.9. A SUBTRACTION GAME 19 from the pile some number of coins belonging to a set S (the subtraction set). Alice goes first. The first player who is unable to make a legal move loses. For example, suppose the initial pile contains 5 coins, and each player can, on his turn, remove any number of coins belonging to the set S = {1, 2, 3}. Who wins? Alice goes first. On her turn she removes 1, 2, or 3 coins from the pile. If she removes 3, then the game reduces to a 2-coin game with Bob going first. Bob wins on his next move. Similarly, if she removes 2, then the game reduces to a 3-coin game with Bob going first, and Bob wins on his next move. But, if she removes 1, then the game reduces to a 4-coin game with Bob going first, and no matter what move Bob makes, Alice wins on her next move. In any subtraction game, the winner can be determined if we know how many coins are in the pile, and which player is next to play. Suppose there are n coins in the pile. If the player next to play take some coins and leave a position from which the opponent (who becomes the player next to play) has no winning strategy, then he can win. If he can not do this, then every legal move leaves a position from which the opponent has a winning strategy, and so the player whose turn it is ca not win. In the table below, we enter N if the player next to play has a winning strategy, and O if the opponent has a winning strategy. The discussion above says that the n-th entry is N whenever there is a legal move so that the entry in the corresponding position is O, and otherwise (the entry corresponding to every legal move is N) it is O/ For the game at hand, we can summarize the winner for each value of n in a table. n 1 2 3 4 5 6 7 8 9 10 11 12 Who N N N O N N N O N N N O In making the table (do it!), a pattern of who wins for which values of n becomes apparent. It is summarized, and proved, below. Example. In the subtraction game with n 1 coins and S = {1, 2, 3}, if n is not a multiple of 4 then the next player to play has a winning strategy, and if n is a multiple of 4 then the opponent has a winning strategy. Basis: If n = 1, 2 or 3, then the next player to play can win on their move by taking all of the coins. Thus the statement to be proved is true when 20 CHAPTER 4. INDUCTION AND RECURSION n = 1, 2, or 3. Induction hypothesis: Suppose that the statement to be proved is true when n is any of 1, 2, . . . , k, where k 3. That is, in each of these situations, if the number of coins in the pile is not a multiple of 4, then the next player to play has a winning strategy, and if the number of coins in the pile is a multiple of 4 , then the opponent has a winning strategy. Induction step: Suppose the pile has n = k + 1 coins. There are 2 cases to consider If k + 1 is a multiple of 4, then any legal move leaves a pile in which the number of coins is not a multiple of 4. By the induction hypothesis, from each of these positions the next player to play has a winning strategy. Hence, in this case, the position in which there are k + 1 coins is such that the opponent has a winning strategy. If k + 1 is is not a multiple of 4, then the next player can remove 1, 2 or 3 coins, as needed, so that the number of coins remaining in the pile will be a multiple of 4. By the induction hypothesis, the opponent has a winning strategy from resulting position. Hence, in this case, the position in which there are k + 1 coins is such that the next player to play wins. Conclusion: By the Principle of Mathematical Induction, for any n 1, if n is not a multiple of 4 then the next player to play has a winning strategy, and if N is a multiple of 4 then the opponent has a winning strategy.

2. 8 Consider the subtraction game described in Section 4.9 of the course notes, but with subtraction set S 11,3). Find, with proof, the situations in which Alice has a winning strategy, and the situations in which Bob has a winning strategy.

Explanation / Answer

Here the set of legal move S= {1,3}

Let alice be A and Bob be B.

let

n=4

the if A goes first then whatever he does he will lose.

If n=5, then

if A goes first and remove 1 the whatever the bob does he will win. if he remove 3 then also whatever B does A will win.

for n=6

if A goes first then if he take 1 coin, we have 5 coins left now then if BoB goes for 1 or 3 he will win no matter what A does the next move. if A take out 3 in the 1st move, then also B will win.

For n=7

if A goes first and take and take 1, then no matter what B does A will win the game.

for n=8

If A goes first then no matter what B does he will win.

Thus from the above we can see that if n is even, then the oppenent will win and if n is odd then the Next to play wins (ie., the starting player) wins.

let us prove this by taking n=K,

if K is odd,

after some equal number of moves (always even either 1+1,1+3,3+3) by each player, we wiil be left with odd number of coins which are either 7 or 5 and the person to play next will be the one who started the game and no mater what he or the opponent does, he will win.

Similarly if K is even,

after some equal number of moves (always even either 1+1,1+3,3+3) by each player, we wiil be left with odd number of coins which are either 4,6 or 8 and the person to play next will be the one who started the game and no mater what he or the opponent does, he will lose.

Thus the strategy for Alice or Bob is to start the game if the n is odd and let the opponent start if n is even, when S={1,3}.

n 4 5 6 7 8 who wins O N O N O

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.