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. * Earth traveler's puzzle

Start from a place on earth surface, you travel south for 100 miles, east for 100 miles, and finally north for 100 miles and you get back to your starting point. Where did you start?

If you get the answer in less than 3 minutes, it's probably NOT right. # Click here to see why.
There are more than one place that can be the starting point !

### Hint

2. * Hat 1, part 1 (Source: New York Times. It also said to appear in the elevator of UC Berkely Math department)

Three people are trying to win the following game as a team:
Each of them is put on a hat of either red or blue with i.i.d probability of 1/2. (i.e. equal chance of being red and blue, and what's put on one person doesn't affect what are on the other people.) Each one can only see the other people's hats, but not his own. He has to guess the color of his own hat by writing down either "Red", "Blue", or "Don't know". After all three people write down their guesses, they would win if:
1. At least one of them guessed right, and
2. None of them guessed wrong.
Note: "guessed right" is defined as guessing a color that is the color of the hat. "guessed wrong" is defined as guessing a color that is NOT the color of the hat. It's neither "right" nor "wrong" if "don't know" is guessed.

Those three people can discuss a strategy before the hats are put on their heads. After the hats are on, they can't communicate to each other including seeing other's guess. What strategy would give them the best chance of winning and what's the probability of winning under that strategy?

## Hint: the optimal winning probability

*** Hat 1, part 2: What happens if there are 7 people, or in general, 2^k - 1 people?

3. * Hat 3

A teacher puts on 10 hats of either red or blue on 10 students. Each one can see the hats on all other 9 students, but not his own. The teacher tells them that at least one of the hat is blue. The teacher asks each one to write down the color of his hat if he's sure about it, or he can write down "don't know" if he can't deduce its color. Everyone reveals their answer at the same time and all of them write "don't know". The second day, they gather again and the teacher puts on the same hats. Each one has to think about the color of his hat again. This time, still no one can figure out his hat color (i.e. everyone writes down "don't know"). This game repeats in the same way on third day, forth day, ..., until the ninth day. Still no one figures out. However, on the tenth day, everyone writes down the correct color of his hat. So explain what happened? And what's the color they wrote down? Assume throughout the 10 days, those students do not communicate with each other. And also assume everyone is smart and knows everyone else is smart, and so on. (See what "so on" means, rigorously.)

4. * 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

5. * Airplane seating problem (source: Ke Yang)

100 passengers are boarding an airplane with 100 seats. Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order. However, the first passenger lost his ticket so he just take a random seat. For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat. What's the probability that the last passenger would sit on his own seat? There is a very simple explanation for the result.

# Hint: see the probability

6. * Horse race (Source: Xinmei Cai)

There are 25 horses and you need to figure out the three fastest horses by placing them into races. Assume there is no tie in the speed. There are five tracks so for each race, you can place five horses and figure out the relative rank among those five horses but you don't have the exact finishing time, i.e. there is no direct comparison between results from two different races. What's the minimum number of races you need to arrange in order to figure out the three fastest horses?

## Hint: see the number races needed

7. * Figure out the connections, part 1 (Source: Xinmei Cai)

There are 66 wires connecting from the top floor to the ground floor. You can see the ends of the wires but you don't know which one on the ground floor connects to which one on the top floor. You can tie the ends of several wires together and test the connections at the other end by using a bulb and battery. For example, if you first tie wires A, B, and C together at the ground floor and then go up to the top floor, you will figure out that the bulb will light if you put it between A and B, A and C, or B and C. You can do the reverse thing by tying the ends at the top floor and test on the ground. Assume you start at ground floor with none of the wire tied, what's the minimum number of trips up and down you need to make before you can figure out all the connections from the ends on the top floor to the ends on the ground floor, which is a one-to-one mapping between them?

## Hint: see the number of trips needed

* Figure out the connections, part 2:

What happens if there are 67 wires? Or any number of wires?

## Hint: see the number of trips needed

8. * A smart blind man (Source: Alex Yang)

(Unfinished. Do not work on it now.) Four glasses on a rotating table. Each time, they end up at north, south, east, west each. A blind man can dicates the flipping of the glasses depending on the direction they are. It ends when all of them are face up. Each time after flipping, someone randomly rotates the table. ...

9. * An old interview question (source: Microsoft interview)

A stick burns out in one hour from one end to the other. How do you measure 45 minutes using two such sticks? Note that sticks are made of different material and the burning speed along different sections are different so you can't use the length of the burnt section to estimate time.

10. * Destructive testing (source: Xiaolei Yao)

There is a building with 100 stories. You want to test how much impact a particular type of cell phone can sustain when dropped from a certain floor. Assume there is a floor x < 100 such that the cell phone will broke when dropped from floor x or any floor above it and it won't broke when dropped from a floor below x. You have two cell phones to spare. How do you design a testing strategy so that you can determine x by the fewest number of drops. Note that you can do test by dropping the cell phone from any floor, but a cell phone can't be used anymore if it's broken.

## Hint

11. * The hardest math-24 puzzle (source: Alex Yang)

How do you apply +, -, *, /, (, ) on 3, 3, 8, 8 to get 24? Each number can only be used once. For example with 2, 2, 8, 8, we have (2 + 2) * 8 - 8 = 24. However, 3, 3, 8, 8 is considerably harder.

Solution