Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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 '11 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 '11 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 '11 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 '11 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 '11 at 8:46
show 6 more comments

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

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Browse other questions tagged or ask your own question.