Number of coins to pickup in the beginning to ensure a definite win : Coins Game

Question

$A$ and $B$ were playing a game which involved picking up coins from a table. Each player in his turn was to pick a minimum of $2$ and a maximum of $6$ coins, except when there is only $1$ coin left in which case, he has to pick up that coin. The game continues till all the coins are removed from the table. The last person to pick up the coin loses the game.
If the game starts with $60$ coins and it is $A's$ turn to pick first, then how many coins should he pick to ensure his win?

Now I wasn't able to do much with this problem and stuck with this problem but what I figured out that if there would have been $9$ or $10$ coins in the game, no matter with whatever number of coins $A$ would have started the game, he would have lost ultimately. But I am not sure that if this is of importance relevant to this problem.
Please help me on this !!!

Thanks in advance !

Answer 1

As mentioned by Teresa Lisbon in the comments, the trick here is to work backwards.

Since you do not want to be the person to pick up the coin(s) when there are $1$ or $2$ coins left, you want to make sure that you are the person to pick up the coins when there are $3, 4, 5, 6, 7$ or $8$ coins left on the table.

Using this knowledge, we can work backwards. What I have done below is I have imagined the coins to have been stacked on top of each other:

$$\begin{array}{|c|c|c|c|} \hline \quad\quad 60 \quad\quad\\ \hline 59\\ \hline 58\\ \hline 57\\ \hline 56\\ \hline 55\\ \hline 54\\ \hline 53\\ \hline 52\\ \hline 51\\ \hline 50\\ \hline 49\\ \hline 48\\ \hline 47\\ \hline 46\\ \hline 45\\ \hline 44\\ \hline 43\\ \hline 42\\ \hline 41\\ \hline 40\\ \hline 39\\ \hline 38\\ \hline 37\\ \hline 36\\ \hline 35\\ \hline 34\\ \hline 33\\ \hline 32\\ \hline 31\\ \hline 30\\ \hline 29\\ \hline 28\\ \hline 27\\ \hline 26\\ \hline 25\\ \hline 24\\ \hline 23\\ \hline 22\\ \hline 21\\ \hline 20\\ \hline 19\\ \hline 18\\ \hline 17\\ \hline 16\\ \hline 15\\ \hline 14\\ \hline 13\\ \hline 12\\ \hline 11\\ \hline 10\\ \hline 9\\ \hline 8\\ \hline 7\\ \hline 6\\ \hline 5\\ \hline 4\\ \hline 3\\ \hline 2\\ \hline 1\\ \hline \end{array} \begin{array}{|c|c|c|c|} \hline \quad\quad \color{green}{60} \quad\quad\\ \hline \color{green}{59}\\ \hline \color{red}{58}\\ \hline \color{red}{57}\\ \hline \color{green}{56}\\ \hline \color{green}{55}\\ \hline \color{green}{54}\\ \hline \color{green}{53}\\ \hline \color{green}{52}\\ \hline \color{green}{51}\\ \hline \color{red}{50}\\ \hline \color{red}{49}\\ \hline \color{green}{48}\\ \hline \color{green}{47}\\ \hline \color{green}{46}\\ \hline \color{green}{45}\\ \hline \color{green}{44}\\ \hline \color{green}{43}\\ \hline \color{red}{42}\\ \hline \color{red}{41}\\ \hline \color{green}{40}\\ \hline \color{green}{39}\\ \hline \color{green}{38}\\ \hline \color{green}{37}\\ \hline \color{green}{36}\\ \hline \color{green}{35}\\ \hline \color{red}{34}\\ \hline \color{red}{33}\\ \hline \color{green}{32}\\ \hline \color{green}{31}\\ \hline \color{green}{30}\\ \hline \color{green}{29}\\ \hline \color{green}{28}\\ \hline \color{green}{27}\\ \hline \color{red}{26}\\ \hline \color{red}{25}\\ \hline \color{green}{24}\\ \hline \color{green}{23}\\ \hline \color{green}{22}\\ \hline \color{green}{21}\\ \hline \color{green}{20}\\ \hline \color{green}{19}\\ \hline \color{red}{18}\\ \hline \color{red}{17}\\ \hline \color{green}{16}\\ \hline \color{green}{15}\\ \hline \color{green}{14}\\ \hline \color{green}{13}\\ \hline \color{green}{12}\\ \hline \color{green}{11}\\ \hline \color{red}{10}\\ \hline \color{red}{9}\\ \hline \color{green}{8}\\ \hline \color{green}{7}\\ \hline \color{green}{6}\\ \hline \color{green}{5}\\ \hline \color{green}{4}\\ \hline \color{green}{3}\\ \hline \color{red}{2}\\ \hline \color{red}{1}\\ \hline \end{array}$$

I will now shade in $\color {red} {\text {red}}$ the coins which, if they are left in the stack, will lead to you losing. This was done by working backwards from each red coin to make sure you do not end up with those coins left when it is your turn. For example, we do not want to end up with 1 coin nor $2$ coins left, so those will be shaded in red. We will always win if there are $3, 4, 5, 6, 7$ or $8$ coins left as we can always force our opponent to pick a coin or coins when there are $1$ or $2$ coins left, so I will be shading those in $\color {green} {\text {green}}$.

However, with $9$ coins, as you have mentioned, we will lose, since no matter how many coins we pick up, our opponent can force us into a situation with either $1$ or $2$ coins left. The same goes for $10$ coins. By doing this, we notice a trend - as long as we force our opponent onto a red coin, we will win. I would suggest you think through this logically for each red coin, by thinking of what you could do and how your opponent would respond. Remember, both players are looking to win, so your opponent will always pick up as many coins to make sure you lose i.e. force you to land on a red coin.

By doing this, we move up the stack, all the way to the $57$th and $58$th coin being shaded red. The important point to note here is that we want to make sure our opponent always lands on a red coin. This means that when there are $60$ coins in the stack, we want to pick up 2 or 3 coins so that our opponent is left with $58$ or $57$ coins, which will eventually lead to them losing.

Therefore, we have to pick up 2 or 3 coins to ensure we win.

Feel free to validate this answer by, again, thinking of what your opponent could do after you have picked up a certain number of coins. Remember, you must always take as many coins to make sure that your opponent stays on a red coin.

As mentioned by Teresa Lisbon in the comments, I would suggest checking out this TED-Ed riddle for a similar question.

I hope that helps!

Answer 2

If $a$ and $a+1$ are losing positions (that is, the next player to move loses), then $[a+2, a+7]$ are winning positions (because a move can be made that leaves $a$ or $a+1$ coins for your opponent). Hence, $a+8$ and $a+9$ are losing positions, because all possible moves leave your opponent with one of these winning positions. It follows inductively that for $b\ge 0$, $a+b$ is a losing position iff $b\equiv 0,1$ (mod $8$). But $1$ and $2$ are losing positions, so this holds with $a=1$: the losing positions are those where the number of coins, modulo $8$, is $1$ or $2$.

Since $60\equiv 4$ (mod $8$), you are in a winning position, and should take $2$ or $3$ coins to hand your opponent a losing position. Thereafter, if your opponent takes $k$ coins, you take $8-k$... eventually your opponent will have $1$ or $2$ left, and must then lose the game.