8

3

Assume you have a pair number of coins $2n$ with possibly different values, ordered in a line. Let us enumerate the coins as $x_1,x_2,\ldots,x_{2n}$. The coins are not ordered in any particular way.

The game has two players and the first player has to take one coin from the extreme points (either $x_1$ or $x_{2n}$). Then, the second player has to take one coin from the extremes and so on until there are no more coins. The winner is the one who ends up with more money.

It is clear that if $n=1$ then the first player wins or draws. If $n=2$ with a little more work you can prove that the first player has a winning (or draw) strategy and the same with $n=3$.

Does the first player have a winning strategy always?

What is the optimal strategy to maximize the profit?

flag
3 
 This is a classic interview question: first player can always win or draw. This is because the first player can always force the second player to pick from the even-numbered coins or from the odd-numbered coins. – alex Mar 28 2011 at 2:28
5 
 @Gabriel, so, wait - you already knew the first player has a winning strategy? MO isn't for questions to which you already know the answer. Please read the faq. – Gerry Myerson Mar 28 2011 at 3:17
1 
 @Gerry: I didn't know the answer before! I just was excited about how easy alex's solution was. @Alex: you should put your solution as answer so I can give you the credit. – ght Mar 28 2011 at 4:07
3 
 @Gabriel, sorry, I misunderstood your comment. I still submit the puzzle has no research interest and doesn't belong on this website. For what it's worth, this is the first item in Peter Winkler's excellent book, Mathematical Puzzles. – Gerry Myerson Mar 28 2011 at 4:33
2 
 so maybe it is worth asking some further questions: What is the optimal strategy (that guarantees the highest money output)? what happens when the number of coins is odd. What is then the best strategy ? Note that then the first player might loose, as the example 1,3,1 shows. – HenrikRüping Mar 28 2011 at 8:46
show 6 more comments

closed as off topic by Gerry Myerson, Andrew Stacey, Denis Serre, S. Carnahan♦ Mar 28 2011 at 12:29

Browse other questions tagged or ask your own question.