Home

Strategy for a 2 Player Coin Game

1,603.1K Views

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.
Share
SherlockHolmes Expert Asked on 10th August 2015 in Puzzles.
Add Comment
Cancel

    • 2 Answer(s)

    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:

    1. The ultimate losing state satisfies the property P
    2. From a state that satisfies P, it is impossible to move to another state that satisfies P
    3. 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:

    1. The ultimate losing state (1) satisfies P
    2. 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
    3. 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.

    Cancel
    Detective Expert Answered on 10th August 2015.
    Add Comment
    Cancel

    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

    Cancel
    Detective Expert Answered on 10th August 2015.
    Add Comment
    Cancel

    • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.

  • More puzzles to try-

  • Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle