Question: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.
Answer: The idea is to count sum of values of all even coins and odd coins, compare the two values. The player that makes the first move can always make sure that the other player is never able to choose an even coin if sum of even coins is higher. Similarly, he/she can make sure that the other player is never able to choose an odd coin if sum of odd coins is higher.
By following the strategy below, you will always win the game (or get a possible tie).
- Count the sum of all coins that are odd-numbered. (Call this X)
- Count the sum of all coins that are even-numbered. (Call this Y)
- If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
- If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
- If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.
Note that the strategy to pick maximum of two corners may not work.