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
First Player picks 14, now row of coins is
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:
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.
Three people check into a hotel room. The bill is $30 so they each pay $10. After they go to the room, the hotel's cashier realizes that the bill should have only been $25. So he gives $5 to the bellhop and tells him to return the money to the guests. The bellhop notices that $5 can't be split evenly between the three guests, so he keeps $2 for himself and then gives the other $3 to the guests.
Now the guests, with their dollars back, have each paid $9 for a total of $27. And the bellhop has pocketed $2. So there is $27 + $2 = $29 accounted for. But the guests originally paid $30. What happened to the other dollar?
This riddle is just an example of misdirection. It is actually nonsensical to add $27 + $2, because the $27 that has been paid includes the $2 the bellhop made.
The correct math is to say that the guests paid $27, and the bellhop took $2, which, if given back to the guests, would bring them to their correct payment of $27 - $2 = $25.
Once upon a time, in the West Lake village, a servant lived with his master. After service of about 30 years, his master became ill and was going to die.
One day, the master called his servant and asked him for a wish. It could be any wish but just one. The master gave him one day to think about it. The servant became very happy and went to his mother for discussion about the wish. His mother was blind and she asked her son for making a wish for her eye-sight to come back. Then the servant went to his wife. She became very excited and asked for a son as they were childless for many years. After that, the servant went to his father who wanted to be rich and so he asked his son to wish for a lot of money. The next day he went to his master and made one wish through which all the three (mother, father, wife) got what they wanted. You have to tell what the servant asked the master.
The servant said, "My mother wants to see her grandson swinging on a swing of gold."