The Gateway to Computer Science Excellence

0 votes

Let there be a pile of $2018$ chips in the center of a table. Suppose there are two players who could alternately remove one, two or three chips from the pile. At least one chip must be removed, but no more than three chips can be removed in a single move. The player that removes the last chip wins. Does the first player (the player who starts playing the game) have a winning strategy in this game, that is, whatever moves his opponent makes, he can always make his moves in a certain way ensuring his win? Justify your answer.

0 votes

To win the game always the first player need to choose 2 chips. Then whatever the other player chooses, first player needs to manage to get the sequence 2,6,10,14,18,......,2010,2014,2018

Suppose the other player chooses 3, then the first player needs to choose 1. So total chips consumed till now will be 2+3+1=6.

Again if the other player chooses 2, then the first player needs to choose 2. So total chips consumed till now will be 6+2+2=10.

In this way, the first player eventually reaches 2018(the last chip).

Suppose the other player chooses 3, then the first player needs to choose 1. So total chips consumed till now will be 2+3+1=6.

Again if the other player chooses 2, then the first player needs to choose 2. So total chips consumed till now will be 6+2+2=10.

In this way, the first player eventually reaches 2018(the last chip).

0 votes

If there are $n$ chips/stones/coins/tokens in a pile/bag/heap and there are $2$ players : Player $1$ and Player $2$. Players can remove minimum $\textbf{a}$ chips from the pile and maximum $\textbf{b}$ chips from the pile. Assuming Player $1$ goes first and the player that removes the last chip from the pile wins and both players play optimally.

Now,

$1)$ if $0 \leq n\; \% \;(a+b) < a$ then Player $2$ has a winning strategy.

$2)$ if $a \leq n\; \% \;(a+b) \leq a+b-1 $ then Player $1$ has a winning strategy.

$3)$ if $0 \leq n < a$ then Player $2$ will win because player $1$ can't remove chips.

To understand how these things came, consider there are $16$ chips and minimum chips a player can remove is $1$ and maximum chips a player can remove is $3$. Now, divide the $16$ chips into slots of $1+3 = 4$ chips slot. I have chosen these $4$ chips slot because in this $4$ chips, if a player chooses $1,2,3$ chips then he/she leaves $3,2,1$ for the other player. So, we can make the strategy for slots of these $4$ chips. Now, we have slots of $4$ chips.

Now for a particular slot,

if player $1$ chooses $1$ chip then player $2$ will choose $3$ chips

if player $1$ chooses $2$ chips then player $2$ will choose $2$ chips

if player $1$ chooses $3$ chips then player $2$ will choose $1$ chips.

It will continue for al the slots and at the end, Player $2$ will have to remove chip. So, here, player $2$ will win the game. So, if no. of chips are multiples of slot size which is $a+b$ then player $2$ will always win.

Now, suppose, there are $17,18$ or $19$ chips then player $1$ will choose $1,2$ or $3$ chips respectively and make the turn to Player $2$. Now, player $2$ and player $1$ will continue in slots of $4$ chips one by one and at the end player $1$ will remove last chip(s) and wins the game. So, here when $1 \leq (n=17,18,19) \% (1+3) \leq 3$ then player $2$ will have a winning strategy.

Now, in the given question, $n=2018, a= 1, b=3$. So, $1 \leq 2018 \% (1+3) \leq 3$, So, $1^{st}$ player has a winning strategy.

52,345 questions

60,483 answers

201,812 comments

95,288 users