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.
A man was to be sentenced, and the judge told him, "You may make a statement. If it is true, I'll sentence you to four years in prison. If it is false, I'll sentence you to six years in prison." After the man made his statement, the judge decided to let him go free.What did the man say?
He said, "You'll sentence me to six years in prison." If it was true, then the judge would have to make it false by sentencing him to four years. If it was false, then he would have to give him six years, which would make it true. Rather than contradict his own word, the judge set the man free.
A wise man lived on a hill above a small town. The townspeople often approached him to solve their difficult problems and riddles. One day, two lads decided to fool him. They took a dove and set off up the hill. Standing before him, one of the lads said "Tell me, wise man, is the dove I hold behind my back dead or alive?" The man smiled and said "I cannot answer your question correctly". Even though the wise man knew the condition of the dove, why wouldn't he state whether it was dead or alive?
The man told the two lads, "If I say the dove is alive, you will the bird and show me that it is dead. If I say that it is dead, you will release the dove and it will fly away. So you see I cannot answer your question.
Search: Schrödinger's cat
A boat has a ladder that has six rungs, each rung is one foot apart. The bottom rung is one foot from the water. The tide rises at 12 inches every 15 minutes. High tide peaks in one hour. When the tide is at it's highest, how many rungs are under water?