Use induction 1. Nim Nim is a two-player game of particular interest to mathemat

Question

Use induction

1. 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 a") and one with 7 ("pile B"). On her first turn, Alice might choose to take 4 coins from pile ?; now ? 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 a, leaving a with 0 coins and ? with 3. Finally, Bob takes the remaining 3 coins from pile B, 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

Yes the second Player can always win if there are initially equal number of coins in both the piles.

The second player has to follow the strategy that the 2nd player follows whatever the first player does in any pile and the second player will always try to bring both the piles to equal numbers.

Eg:

If both piles have initially have 7 coins each the whatever the 1st player removes from any pile the second player intimate that move from the other pile.

Suppose 1st player removes 4 coins, then the configration becomes 3,7. The second player will try to bring same coin configration back by removing 4 from the second pile and in the end forcibly player 1 has to finish a pile so that the 2nd player finishes the other pile and wins.

We will now prove this by induction.

Suppose both Piles have k coins.

we see for k=1,2 it is trivially correct and the second player always has a winning strategy.

Assume it to be true for all values upto some K=k.

Now for k+1 the After the first player removes some coins from either of the pile. And the number of coins in this pile now becomes less than or equal to k.

So the second player in his move removes the same number of coins from the other pile so that both piles now have the same number of coins and the count of the coins is less than or equal to k.

So the problem is now reduced to an equivalent problem with a smaller k which is true(assumed).

So, by principle of induction, We can say that the second player always have a winning stratergy if there are equal number of coins.

B)

Suppose, now there are unequal number of coins. The first player can always remove coins from the pile which has greater number of coins so that now both the piles have the same number of coins.

So the next turn is of the second player and he being on the starting move if both the piles have the same number of coins, the the first player always repeat the above process, i.e. remove the same number of coins from the other pile which the opponent is removing. So, the First player in this case, always has a winning stratergy.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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