Recurrence Nim Nim is a two-player game of particular interest to mathematical g

Question

Recurrence

Nim Nim is a two-player game of particular interest to mathematical game theorists. In one variant of Nim, there are two piles of coins. The game has two players, who alternate turns; on each turn, each player chooses one pile, and takes some (positive) number of coins from the pile Whoever takes the last coin wins the game For example, suppose Alice and Bob are playing a game of Nim with Alice playing first Suppose they have one pile with 9 coins (call this "pile ") and one with 7 ("pile B). On her first turn. Alice might choose to take 4 coins from pile : now a has 9 coins, and has 3. Now Bob gets a turn; perhaps he chooses to take 3 coins from pile a. Now a has 6 coins, and has 3, Alice next chooses to take all 6 coins from pile , leaving a with 0 coins and with 3. Finally, Bob takes the remaining 3 coins from pile , and wins (a) Prove that if both piles initially contain the same number of coins, then the second player always has a winning strategy (Hint: use induction on the number of coins in the piles.) (b) Prove that if both piles initially have different numbers of coins, then the first player always has a winning strategy (Hint: use part (a).)

Explanation / Answer

Let P(n) be “In a game of Nim, if both piles of coins have n coins each and it’s the rst player’s turn, the second player can always win.”

We show that P(n) holds for all n N, using strong induction on n.

Base case : If both piles have 0 coins in them, the rst player loses according to the rules of the game. Thus, the second player always plays ‘correctly’ by doing nothing, and wins, so P(0) holds.

Induction hypothesis : Assume that for some nonzero n N, P(i) is true for 0 i < n. This means that in any game of Nim, if both piles of coins have i coins each and it’s the first player’s turn, the second player can win , for 0 i < n.

Induction step : We show that P(n) holds.

Consider a game of Nim in which there are two piles of coins, A and B, with n coins in each. Without loss of generality, let A be the pile that the rst player chooses to remove coins from. The rst player must remove k coins from pile A such that 1 k n, leaving nk coins in pile A and n coins in pile B. If the second player removes k coins from pile B, this leaves two piles with nk coins in each. It is now the rst player’s turn.

By the induction hypothesis, the second player can now win this game because there are two piles with nk coins in each, 0 nk < n, and it is the rst player’s turn.

Thus, the second player has a strategy by which to win a game of Nim with n coins, and P(n) holds, completing the induction.

(b) Follow the steps in part (a) to prove "if both piles initially have different numbers of coins, then the first player always has a winning strategy."

If first player takes k1 coins from pile A, then pile A will be left with n1-k1 coins.

the second player will take k2 coins from pile B, then pile B will be left with n2-k2 coins.

To win, first player will take a few coins with somecoins left behind. Second player will take all the remaining coins from pile B . So, first player will take coins from pille A and the player wins. Prove this using induction as in part (a)

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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