Game theory (Part 2)
I will show you the problem that my teacher used as a practice for my team to participate in the City Round for Mathematic Gifted Students. I struggled at the first time but was able to find the solution due to observing some minor details:
Given 2024 candies on the table. 2 students alternatively pick the candies and the numbers of candies that they are able to pick are 1,2, and 6. Whoever picks the last candy is the winner. Assume both are clever enough to find his/her way to beat the opponents. Who will have the strategy to win this game?
At first, sitting in the class thinking about this problem, I tried some rules like if the first pick “a” then the second pick “10-a” or somehow like that. But my problem was that I have assumed the game had only 1 winning person. So then I tried cases with a small number of candies (something that is very popular in the IMO problem-solving). When you cannot solve a problem, you may try some easy and small cases:
If n=1 or 2, the first person will win.
If n=3, whether the first pick 1 or 2, the second can pick the rest to win this game (I am wrong to assume there is a default winner)
If n=4, the first person can pick 1 candy in his/her first round, pushing the second player into the n=3 situation similar to n=5.
If n=7 (n=6 is too obvious), as when the first pick (1,2,6), the second got left (6,5,1) and the second always has a way to win.
You pick some more cases like n=8 or n=9,...
Looking at the board of winners, you can really easily see that in small cases, the 2nd person wins when the n=3,7,10,14 or when n leaves the remainder of 2 when divided by 7, the 2nd person will have the strategy to win. In other cases, 1st person has the strategy to win.
Let’s prove it with induction:
