Puzzle : Coin passing game

Hello all,
The problem I am about to post seems to be popular amongst puzzle lovers. Me
and Saket settled it when we came across it yesterday. Not a hard puzzle but needs just a
couple of observations to solve.

Problem : There are n persons sitting in a circular fashion. Each of them owns a coin.
First person passes 1 coin to the person sitting on his left side. The second person in
turn passes 2 coins to the person sitting on the left. Third person passes 1 coin to the
left, 4th passes 2 coin to his left and so on. So each person receiving 1 coin from the
right has to pass 2 coins to the left. Similarly, a person receiving 2 coins from the
right has to pass 1 coin to the left. If at any point of time, a person runs out of coin
he/she is thrown out of the game. Convince yourself that it can never happen that a person
having 1 coin has to pass 2 coin to his left.

A game is called terminating if at the end only 1 person is left with all the coins in
his/her possession. There might be values of n where the game may not terminate e.g. 3
persons left with 4 4 4 coins respectively.

Prove that there are infinitely many values of n for which the game terminates.

Solution : If you start observing behaviour of games starting from n=1, you can observe
patterns which you can generalize.

It is easy to see that in the first round each person sitting at an even numbered position
will be thrown out of the game as he/she has 1 coin initially, receives 1 coin from right
but has to now pass both the coins to the left.

Also observe that the 1st person will be always thrown out of the game ( poor guy !! )

If n = 2k, after the first round k-1 will remain. If n = 2k+1, then k will remain.

Case 1 : n is even
for n=2k , after the first round configuration would look like

3(4) 5(2) 7(2) … 2k-1(2)

where a(b) denotes position a with b coins.
at this point of time. Number of remaining people are k, if k is odd the game will not
terminate because a person who looses one coin in a round will gain one coin in the next
round.

Case 2 : n is odd
for n=2k+1, after the first round configuration would look like
3(3) 5(2) … 2k+1(2)

If k is odd, the game will not terminate.

If both the cases if k is even, at the end of two rounds exactly half will remain. Because
a person who looses a coin will keep loosing in subsequent round.

After this elimination you again have to deal with cases where remaining people are odd or
even.

Thus you can observe that if after the first round 2^k people remain then the game
will always terminate. This can happen if initially there are 2^k + 2 or 2^k + 1 person are there.

Not a very challenging puzzle, but interesting enough.

— Saurabh Joshi

Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: