Some problems are used during job interviews by technology and financial companies.

Level: * Difficult      ** Very difficult      *** Extremely difficult

Hint: # Trivial hint. Check it after 10 minutes.      ## Moderate hint      ### Substantial hint. But still require a lot of thinking.

I will check the correctness of your solution if you email it to .
I will make it publicly available and acknowledged under your name upon your consent.

Note: all problems are well-defined and rigorously solved. No wording or semantic tricks exploiting metaphor or ambiguity.

1. ** Better than random (source: David Vickrey)

You are given two boxes with a number inside each box. The two numbers are different but you have no idea what they are. You pick one box to open; read the number inside; and then guess if the number in the other box is larger or smaller. You win if you guess correctly, and lose otherwise. Is there anyway that you can win the game with more than 50% chances no matter what the two numbers are?

# Hint

2. ** Hat 2

100 people is seated in a column. Devil puts a hat of either red or blue on everyone's head. Everyone can only see the hats of all the people sitting before him. Each one has to say the color of his own hat, starting from the one sitting on the last seat who can see the hats of all 99 people before him, but not his own. He would be killed if he guessed wrong. After the last one guessed, the 99th person would guess. All his information is the hats on the 98 people before him and what the last one guessed, which he can hear. He would also be killed if he guessed wrong. Each person guess in turn till the person sitting on the first seat. Each one's information is the hats of people before him and what the people after him guessed. Those 100 people can get together and devise a strategy before the Devil puts on the hats. Devil would know their strategy and try to put on the hats so he can kill as many people as possible. What's the best strategy those 100 people can come up with to minimize the total number of people being killed? Assume everyone is unselfish and works together for this common goal.

## Hint: see the minimum number of people killed

3. * Pirates' democracy, part 1

100 pirates needs to allocate 100 identical laptops among them. Their democratic system works as follows:
All pirates are ranked by their seniority. First, the most senior pirate (called "Majority leader") propose an allocation plan that states exactly how many laptops each pirate would get. The 100 pirates would vote on the plan (no filibuster) and it would pass if more than or equal to half pirates voted for it. If it passes, pirates take their laptops and go home. If it fails, the one who proposed the plan (the most senior pirate in this case) would be killed, and then the second most senior pirate would take the place of "Majority leader" and propose his plan. We repeat the same process above in the order of seniority until someone's plan is passed.

Assume every pirate makes his decision based on the following priorities:
1. He doesn't want to die.
2. Given he's not going to die, he would prefer to get as many laptops as possible.
3. Given he's going to get the same number of laptops, he would prefer as many other pirates to die as possible.

Also assume every pirate is smart and knows everyone else is smart, and so on. (See what "so on" means, rigorously.) What will happen? i.e. whose proposal will be passed and what is the proposal?

## Hint

** Pirates' democracy, part 2:

What happens if there are 435 pirates (but still only 100 laptops)? This is qualitatively more difficult than the case with 100 pirates.
(There is nothing magic about 435. It's just the number of Representatives.)

# Hint

4. ** Unfair GoBang (I believe this problem never appeared elsewhere.)

GoBang is an oriental chess game, also called 5-in-a-Row. Here we consider a modified version:
The board is a grid extending infinitely to all four directions. In each turn, player A puts two black stones on the board while player B puts down only one white stone. Player A wins if 1000 of his black stones form a consecutive line (either vertical, horizontal, or diagonal). Player B tries to block A from achieving that goal. However, player B himself can never win (i.e. the game continues even if 1000 of his white stones form a line). Show that player A has a strategy so that he can always achieve the goal and win, no matter how player B plays.

5. ** Swimming dog and tiger

A dog is in the center of a round swimming pool. A tiger, who can't swim, is on the edge of the wimming pool and tries to catch the dog. What's the maximum ratio of the tiger's running speed and the dog's swimming speed given that the dog can swim ashore without being caught by the tiger? What's the strategy (i.e. swimming route) the dog should use?

Note: this problem can be solved by differential equation. However, there is an elegant solution using only elementary math. Unfortunately, I am not aware of any closed form analytic solution.

6. ** World's hardest elementary geometry problem

What's the degree of angle 'a'?

According to Hai Huang, this problem appears in American Airline in-flight magazine. Does AA assume its passengers have IQ > 150 ?!

7. ** Truth from a liar (Okay, this may be the only problem that you may argue the solution is not so rigorous.)

There is only one person on an island. He either always tells the truth or always lies, but you don't know which is the case. You reach an intersection and don't know if you should turn left or right. You can only ask him one "Yes/No" question. What question should you ask so you can figure out the direction you need to go?

8. ** Survival of the smart prisoners, part 1 (Source: Xiaolin Xie)

100 prisoners are held incommunicado in a jail. They are being brought into a court room randomly. Each time they enter into the court, they can either turn on or turn off the light. Initially the light is off. Assume each prisoner will be brought into the court for many times and no two of them will be in the court at the same time. At any time, a prisoner can claim that each of the 100 prisoners has been in the court room for at least once. They will all be released if the claim is correct and put to death if it's wrong. These 100 prisoners could devise a strategy before they went to the jail. How could they guarantee their freedom eventually?

** Survival of the smart prisoners, part 2:

What happens if the initial state of the light is unknown?