5
$\begingroup$

$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 !

$\endgroup$
10
  • 3
    $\begingroup$ Work backwards, using the idea of losing and winning positions. See this TED-ED riddle for a similar question. Basically, the idea is that you need to start with this : if the number of coins when anyone's turn finishes is $0$, then that person is a loser. If the number of coins when anyone's turn finishes is $1$, then that person is a winner : and now you need to try and make moves that direct you to winning and losing positions. Either way, the riddle's answer will make plenty of sense (as do many TED-ED riddles!) $\endgroup$ Jun 10 at 7:04
  • 1
    $\begingroup$ @TeresaLisbon The only thing that makes this one slightly different from the standard Nim game is that there are two winning positions with a small number of coins - you can win by leaving 1 coin, but also by leaving 2 coins. The rest of the analysis is the same, but it means there will be two possible winning first moves. $\endgroup$ Jun 10 at 7:29
  • 1
    $\begingroup$ @TeresaLisbon : Thanks but I already follow few of these channels such as Numberphile, Mind Your Decisions, Michael Penn, 3Blue1Brown, blackpenredpen, Stand Up Mathematician,etc. And also I am not a mathematics student full time but I like it so that's why I watch and solve problems like this sometimes. Yeah I wasn't knowing about the TED-ED Riddles, thanks for that ! $\endgroup$
    – Ganit
    Jun 10 at 8:32
  • 1
    $\begingroup$ @Ganit I wish to provide an answer, but I still think your question lacks a little on-site quality (this may be me and no one else, but I don't want to take a chance). Can I ask you to add a few things to your post so that we can qualify your question as being on-site, and then proceed? In particular, I want : a source of the question and the reasoning that lead you to what would happen if $9/10$ coins were in the game (in brief detail). Your working is of relevance because I will critique it in my answer, for example, so I'd be happy if it were provided. $\endgroup$ Jun 10 at 8:56
  • 1
    $\begingroup$ Let's say there are $9$ coins, then if in the beginning $A$ picks up $6$ coin then $B$ will pick $2$ coins and at the last $1$ coin will be left which will have to be picked up by $A$ and hence $A$ will loose. In symbols form, let us say $9 =6+2+1.$ Similarly :- <br> $9 =5+3+1$ <br> $9=4+4+1$ <br> $9=3+5+1$ <br> $9 = 2 +6 +1$. So you can see with whatever coins $A$ will begin with $B$ can always pick in such a way that $A$ will have to pick $1$ coin in the last and he will loose. Similarly I have analyzed for $10$. $\endgroup$
    – Ganit
    Jun 10 at 9:24
3
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Why do you have two runs of $6$ greens, but runs of $7$ greens after that? $\endgroup$
    – mjqxxxx
    Jun 10 at 13:53
  • $\begingroup$ @mjqxxxx My apologies, it was an error made when the diagram was created. I have edited the answer accordingly. Thank you very much for bringing it up. :) $\endgroup$ Jun 10 at 14:35
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Note that OP’s observation, that $9$ and $10$ are losing positions, is exactly right and shows the start of this mod $8$ periodicity. $\endgroup$
    – mjqxxxx
    Jun 10 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.