Linear Programming and Operational Research Question, Dynamic Programming

a) Suppose there are 40 pennies on a table. I begin by removing 1,2,3, or 4 pennies. Then my opponent must remove 1,2,3, or 4 pennies. We continue alternating turns until the last penny is removed. The player who picks up the last match is the loser. Can I be sure of victory? If so, how?

b) If there are initially N pennies and each player removes 1,2,..., or k pennies , are there values of N and k for which I can't be guaranteed a victory? Find such a pair of values or show that I have a winning strategy no matter how many N and k are selected

Thank you so much who ever can help me!!

Quote:

---

Originally Posted by Phyxius117

a) Suppose there are 40 pennies on a table. I begin by removing 1,2,3, or 4 pennies. Then my opponent must remove 1,2,3, or 4 pennies. We continue alternating turns until the last penny is removed. The player who picks up the last match is the loser. Can I be sure of victory? If so, how?

---

Suppose you could play so the at some point you leave your opponent 6 coins, The most he can then take is 4 leaving 2, from which position you win by taking 1 leaving 1.

On an earlier move if you leave 11 you can force the game so that subsequently you can leave 6, since the most he can take is 4 he must leave you 7, abd the least he can take is 1 leaving you 10, from both these positions you can on the next move leave 6.

Repeat the argument backwards through the game, so you reach the point if you leave him 36 you have a winning strategy of progressivly leaving your opponent 31, 26, 21, 16, 11 and 6.

CB