Consider the following game: the game starts with n coins laid out on a table (

Question

Consider the following game: the game starts with n coins laid out on a table (n 1, n ). Two players take turns removing coins from the table. During a single turn, a player may choose to remove either one or two coins from the table. A player wins the game by being the one to take the last coin. Prove by strong induction on n, that if n is divisible by three, then the second player to move can guarantee a win, and if n is not divisible by three, then the first player to move can guarantee a win.

Explanation / Answer

Say the table has 3 coins.

Then if the first player removes 1 coin, II removes 2 and wins. Or if I player removes 2 coins, 2nd removes last coin and wins.

Hence for 3(1) this is true.

Let us assume true for 3(k)

Then to prove for 3(k+1)

For 3k coins the second player removes the last coin, now again 3 coins are in the table. So ii player can win easily.

Thus by induction, we find that for multiples of 3, II person can win.

-----------------------------------

Not a multiple of 3:

Let it be 4. Then first player takes one coin, now 3 are there, with second person starting. Hence first player can win.

So if n = 3m+1, first player can win if he removes one coin in the first round.

If it is of the form 3m+2, then in the first round, if first player removes 2 coins, then the second starts with 3m. Hence first player only will win.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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