Strategy for a 2 Player Coin Game
Consider a two player coin game where each player gets turn one by one. There is a row of even number of coins, and a player on his/her turn can pick a coin from any of the two corners of the row. The player that collects coins with more value wins the game. Develop a strategy for the player making the first turn, such he/she never looses the game.
Note that the strategy to pick maximum of two corners may not work. In the following example, first player looses the game when he/she uses strategy to pick maximum of two corners.
Example 18 20 15 30 10 14 First Player picks 18, now row of coins is 20 15 30 10 14 Second player picks 20, now row of coins is 15 30 10 14 First Player picks 15, now row of coins is 30 10 14 Second player picks 30, now row of coins is 10 14 First Player picks 14, now row of coins is 10 Second player picks 10, game over. The total value collected by second player is more (20 + 30 + 10) compared to first player (18 + 15 + 14). So the second player wins.
The first player loses iff n=6k+1
If n=1, the first player is forced to take it and hence loses. Now that we have identified a losing position, it makes sense to send the opponent to the losing position. Hence if n=2,3,4,5 or 6, the first player can take away n-1 coins and give just 1 coin to the opponent, forcing them to lose.
If n=7, anything that the first player does, the opponent is going to end up with 2,3,4,5 or 6 coins. But as explained earlier, the opponent can then take away the required number of coins to give a single coin to the first player, forcing them to lose. Thus n=7 is a losing position, from which it follows that n=8,9,10,11 and 12 are winning positions.
By induction, it can be proved that numbers of the form 6k+1 are the losing positions. In general, in an impartial game that is acyclic and guaranteed to end in a win for one player, here is the procedure to find out which states are winning positions for the first player. Suppose that there is a property P that you can assign to some of the game states such that:
- The ultimate losing state satisfies the property P
- From a state that satisfies P, it is impossible to move to another state that satisfies P
- From any state that does not satisfy P, it is possible to move to some state that satisfies P
In such a case, the P states are exactly the losing states.
For this problem, let us define the property P for states (integers for us) as n leaves remainder 1 on division by 6. Then it is easy to see that:
- The ultimate losing state (1) satisfies P
- From a number that is 1 modulo 6, it is impossible to obtain another one by subtracting 1,2,3,4 or 5. That is, We cannot move from a P state to another
- From a number that is 0,2,3,4 or 5 modulo 6, we can subtract 5,1,2,3 and 4 respectively to obtain a number which is 1 modulo 6. That is, from any non-P state, we can move to a P-state
Hence the only losing states are those with integers that are 1 modulo 6.
Player 1 picks the first coin from right end and player 2 picks coin which have higher value from either end in next step player 1 can continue to pick up higher value coin from either end
Your Answer
More puzzles to try-
Find the missing Number
Find out the missing number in the picture attached:Read More »Boolean Enlightenment
The path to enlightenment lies behind one of two doors. In front of each door stands a guard who knows ...Read More »Smallest Number Game
Which is the smallest number that you can write using all the vowels exactly once?Read More »Day of the week
A group of campers have been on vacation for a long, that they have forgotten the day of the week. ...Read More »Who is youngest
On a bus, there is a 26-year-old pregnant lady. A 30-year-old policeman. A 52-year-old random woman. And the 65-year-old driver. ...Read More »Father and Grandfather Age Puzzle
A boy asks his father, ” what is the age of grand father?”. Father replied “He is x years old ...Read More »what appears to be spokes moving around with your eyes?
When you move your eyes in a circular motion around this image, you will see what appears to be spokes ...Read More »To help celebrate the New Year, we’ve decided to give you a New Year’s toast. There’s just one catch….you’ll have to solve the puzzle first!
Answer the clues below to find each word. Then place the letters on the lines below. Each letter must be ...Read More »What would you have?
If you had three apples and four oranges in one hand and four apples and three oranges in the other ...Read More »Can you find out the missing number in the grid?
Can you find out the missing number in the grid?Read More »Man in car riddle
A man is in his car. He sees three doors; a golden one, a diamond one and a silver one. ...Read More »Japan Plus Panama is What
If Japan and Panama decided to merge into a single country, probably people will name it Japanama. Can you think ...Read More »Happiness Always
Where can happiness always be found?Read More »What do the following words have in common?
What do the following words have in common? Assess Banana Dresser Grammar Potato Revive Uneven VoodooRead More »Red and Blue marbles interview puzzle
You have two jars, 50 red marbles, 50 blue marbles. you need to place al the marbles into the jars ...Read More »Five greedy pirates and gold coin distribution Puzzle
Five puzzleFry ship’s pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all ...Read More »Can\’t touch
You can see it everyday, But cannot touch it at will. What is it ?Read More »At first glance, guess which color ants are the most numerous??
With a neck but no head
Who is with a neck and no head, two arms and no hands?Read More »Fastest driving riddle
Two friends were driving from their home to Manchester, Kevin drove the first 90 miles, and Daniel took over the ...Read More »