You have a sock drawer.
It has 4 black socks, 8 brown socks, 2 white socks and 8 tan socks.
You need to pull out a matching pair of socks in the dark.
There is no light and you couldn't see the socks.
How many socks you should pull out in the dark to get one matching pair of socks?
Five. You have only four different colors of socks. If you pick 5, you can surely get one pair of matching socks.
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.
If you're 8 feet away from a door and with each move you advance half the distance to the door. How many moves will it take to reach the door?
You will never reach the door! If you only move half the distance, then you will always have half the distance remaining no matter, how small is the number.
Count the number of times the letter "F" appears in the following paragraph:
FAY FRIED FIFTY POUNDS OF
SALTED FISH AND THREE POUNDS
OF DRY FENNEL FOR DINNER FOR
FORTY MEMBERS OF HER FATHER'S FAMILY.
It appears 14 times. Make sure to count the "F"s in the word "OF", which people commonly miss.
Tarun Asthnaiya go to his office by local train. However nearby train station is quite far from his place and he used to drive his bike to train station daily with an average speed of 60km/hr. One day at halfway point he relized that due to heavy traffic he got late having average speed of just 30km/hr. How fast he must drive for the rest of the way to catch my local train?
The train is just about to leave the station and there is no way Tarun will be able to catch it this time.
