Game of Coins

So, I am back again with an interesting puzzle. Credit goes to my dear friend Sambuddha Roy to introduce me to this puzzle as well as its very simple solution.

Here goes the puzzle :

Even number of coins are laid out in a straight line. Coins may have different denominations. Two players p1 and p2 are playing a game. When a player's turn comes he/she has to pick a coin from either end of the line. When all the coins are exhausted, player with the highest amount wins. A tie occurs whent both the player possess the equal amount.

Prove that if p1 goes first, he/she always have the stretagy such that he/she does not loose the game.


Solution :

Solution to this puzzle is very simple and I really felt really stupid when I came to know about the solution and its simplicity. As always, I tried to use induction to prove that p1 always have a winning stretagy ( or non-loosing stretagy). For the case when number of coins is 2, p1 can pick the larger of the two. But then things get complicated when we need to prove the induction step. In fact, I did not spend enough time to prove that using induction.

A very simple solution is that p1 can index the coins from 1 to n. Then, he can calculate sum total of odd-numbered coins as well as even-numbered coins. p1 can always pick coins in a way such that he/she always gets even-numbered or odd-numbered coins depending on which of those will make up a larger amount.