A road named NoNameUno

It is one of Phil Collin's best song that I ever heard. If you have not, fire up the Youtube and listen...

But here it is about solving puzzles like problem, prove the solution for correctness, then write a program. These problems are not the ordinary problems we ordinarily deal with like: sorting, searching, max, min, queues, stacks, lists, arrays etc., etc. 

If you solve couple of them on your own, you appreciate the meaning of the song. Yes here she is nothing but Algorithm. So let's get to one such problem.

One thousand coins of different denominations are placed on a large table. They are placed side by side forming a line. You are asked to pick a coin from one of the two ends of the line, then your opponent will pick one from the end of the resultant line. At the end of the process you have to make sure that you win or at least make it a draw and your opponent never wins. Win means you managed to grab more money than your opponent. The only rules for picking your coin from one of the two ends of line, and in case of the last coin, one has to pick that if it is his/her turn.

If you never seen this problem, don't even read the rest, take the problem and try to come up with steps that will guarantee a win or at least a draw. If you seen this type of problem, rest of this article is a waste of time for you!!! By the way, it took me a while to solve this problem.

Give yourself a long pause, and don't try to look further, if clueless then look at the hint only, then stop and go back to your note book to solve it!

Don't read any further .....

Hint: Label the coins' position. You may win if you pick the coins from the odd positioned and you may win by picking the even positioned coins. Further more it could be One million coins or even more than that.

I will send the solution upon request, but if you can solve it by yourself that is the best and treat yourself.

Easy Lover, she'll get a hold on you ...