Four jolly men sat down to play,
and played all night till break of day.
They played for gold and not for fun,
with separate scores for every one.
Yet when they came to square accounts,
they all had made quite fair amounts!
Can you the paradox explain?
If no one lost, how could all gain?

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
Would you rather go first or second? Does it matter?
Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
Note that the strategy to pick maximum of two corners may not work. In the following example, first player looses the game when he/she uses strategy to pick maximum of two corners.
Example 18 20 15 30 10 14
First Player picks 18, now row of coins is
20 15 30 10 14
Second player picks 20, now row of coins is
15 30 10 14
First Player picks 15, now row of coins is
30 10 14
Second player picks 30, now row of coins is
10 14
First Player picks 14, now row of coins is
10
Second player picks 10, game over.
The total value collected by second player is more (20 + 30 + 10) compared to first player (18 + 15 + 14). So the second player wins.

Going first will guarantee that you will not lose. By following the strategy below, you will always win the game (or get a possible tie).
(1) Count the sum of all coins that are odd-numbered. (Call this X)
(2) Count the sum of all coins that are even-numbered. (Call this Y)
(3) If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
(4) If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
(5) If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.
You might be wondering how you can always choose odd-numbered/even-numbered coins. Let me illustrate this using an example where you have 6 coins:
Example
18 20 15 30 10 14
Sum of odd coins = 18 + 15 + 10 = 43
Sum of even coins = 20 + 30 + 14 = 64.
Since the sum of even coins is more, the first player decides to collect all even coins. He first picks 14, now the other player can only pick a coin (10 or 18). Whichever is picked the other player, the first player again gets an opportunity to pick an even coin and block all even coins.

A man is sitting in a pub feeling rather poor. He sees the man next to him pull a wad of £50 notes out of his wallet.
He turns to the rich man and says to him, 'I have an amazing talent; I know almost every song that has ever existed.'
The rich man laughs.
The poor man says, 'I am willing to bet you all the money you have in your wallet that I can sing a genuine song with a lady's name of your choice in it.'
The rich man laughs again and says, 'OK, how about my daughter's name, Joanna Armstrong-Miller?'
The rich man goes home poor. The poor man goes home rich.
What song did he sing?

A man told his son that he would give him $1000 if he could accomplish the following task. The father gave his son ten envelopes and a thousand dollars, all in one dollar bills. He told his son, "Place the money in the envelopes in such a manner that no matter what number of dollars I ask for, you can give me one or more of the envelopes, containing the exact amount I asked for without having to open any of the envelopes. If you can do this, you will keep the $1000."
When the father asked for a sum of money, the son was able to give him envelopes containing the exact amount of money asked for. How did the son distribute the money among the ten envelopes?

The contents or the ten envelopes (in dollar bills) hould be as follows: $1, 2, 4, 8, 16, 32, 64, 128, 256, 489. The first nine numbers are in geometrical progression, and their sum, deducted from 1,000, gives the contents of the tenth envelope.

Three people check into a hotel. They pay $30 to the manager and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room, the bellboy reasons that $5 would be difficult to share among three people, so he pockets $2 and gives $1 to each person. Now, each person paid $10 and got back $1. So they paid $9 each, totalling $27. The bellboy has $2, totalling $29. )
Where is the remaining dollar?

Each person paid $9, totalling $27.
The manager has $25 and the bellboy has $2.
The bellboy's $2 should be added to the manager's $25 or substracted from the tenant's $27, not added to the tenants' $27.

You are on a gameshow and the host shows you three doors. Behind one door is a suitcase with $1 million in it, and behind the other two doors are sacks of coal. The host tells you to choose a door, and that the prize behind that door will be yours to keep.
You point to one of the three doors. The host says, "Before we open the door you pointed to, I am going to open one of the other doors." He points to one of the other doors, and it swings open, revealing a sack of coal behind it.
"Now I will give you a choice," the host tells you. "You can either stick with the door you originally chose, or you can choose to switch to the other unopened door."
Should you switch doors, stick with your original choice, or does it not matter?

You should switch doors.
There are 3 possibilities for the first door you picked:
You picked the first wrong door - so if you switch, you win
You picked the other wrong door - again, if you switch, you win
You picked the correct door - if you switch, you lose
Each of these cases are equally likely. So if you switch, there is a 2/3 chance that you will win (because there is a 2/3 chance that you are in one of the first two cases listed above), and a 1/3 chance you'll lose. So switching is a good idea.
Another way to look at this is to imagine that you're on a similar game show, except with 100 doors. 99 of those doors have coal behind them, 1 has the money. The host tells you to pick a door, and you point to one, knowing almost certainly that you did not pick the correct one (there's only a 1 in 100 chance). Then the host opens 98 other doors, leave only the door you picked and one other door closed. We know that the host was forced to leave the door with money behind it closed, so it is almost definitely the door we did not pick initially, and we would be wise to switch.
Search: Monty Hall problem