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 .
Note: all problems are well-defined and rigorously solved. No wording or semantic tricks exploiting metaphor or ambiguity.
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?
# Hint: the optimal winning probability
### More hint
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.
## Hint: see the probability
### More hint
A philanthropist is going to give you some money. He puts money into two envelopes and one envelope contains twice as much money as the other envelope. However, you don't know which one has more money. You randomly pick one envelope. You open it and find that it has $20. Now you have two options: 1. keep the $20, or 2. exchange the $20 for the money in the other envelope. Assume you are risk-neutral (i.e. your happiness is the expected amount of money and you don't care about risk), which option should you take? Think about this question first for 3 minutes before you continue to read on.
Think about the previous question for 3 minutes before continue reading on ...
The other envelope contains either $10 or $40. So it seems if you exchange, your expected money is ($10 + $40) / 2 = $25 (> $20) and you should take this option because you are risk-neutral. If this is the case, you should exchange whatever the amount of money you find in the envelope by using the same reasoning (i.e. (0.5x + 2x) / 2 > x). This means you should exchange even before you open the envelope. However, this is ridiculous because you randomly picked the envelope and it shouldn't matter whether to exchange or not before you get any information. So how do you explain the paradox?
(Unfinished. Do not work on it now.) The answer can be solved exactly only if we assume and ask for Nash equilibrium, which is not a deterministic strategy in this case.
Go back to Haidong's puzzle page
Go back to Haidong's main page