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

2. *** Find your number (source: David Vickrey. Requires advanced formal math)

There are n people, each with a unique number from 1 to n. There are n identical lockers, each of which contains a paper with a unique number from 1 to n on it. However, you have no idea which locker contains what number. The purpose is for everyone to find the locker with his own number. Each one can open at most n/2 lockers and, once he looks at the number, he has to close the locker. If another person wants to see the same locker, he has to open it again himself. They can't exchange information with each other. Prove that there exists a certain constant that no matter how big n is, those people can always devise a strategy so all of them can find their own numbers with probability larger than that constant.

Note: this is surprising because if everyone picks n/2 lockers independent of other people, the probability that all of them find their own numbers is 1/2^n, which goes to 0 as n goes to infinity.