Marty and Jill want to copy three 60 minute tapes. They have two tape recorders that will dub the tapes for them, so they can do two at a time. It takes 30 minutes for each side to complete; therefore in one hour two tapes will be done, and in another hour the third will be done. Jill says all three tapes can be made in 90 minutes. How?
Jill will rotate the three tapes. Let's call them tapes 1,2, and 3 with sides A and B. In the first 30 minutes they will tape 1A and 2A, in the second 3 minutes they will tape 1B and 3A (Tape 1 is now done). Finally, in the last 30 minutes, they will tape 2B and 3B.
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.
You are standing next to three switches. You know these switches belong to three bulbs in a room behind a closed door – the door is tight closed, and heavy which means that it's absolutely impossible to see if any bulb is on or not. All three switches are now in position off.
You can do whatever you want with the switches and when you are finished you open the door and go into the room. While in there you have to tell which switch belongs to which bulb.
How will you do that?
Turn on the first switch and wait for a while.
Turn off the first one and turn on the second.
Go into the room.
One bulb is shining, the second bulb is hot and the third one nothing.
