Problem Statement
Seven people are chatting at a party. They're told about the rules of this game while they're still chatting (which is as follows). Then they're blindfolded. Someone puts colored party hats on their heads, sits them at a round table, then undoes their blindfolds. They're now able to see each others' hats but not their own. They're not allowed to talk or share notes. They're all asked to each write their own hat color on a piece of paper and submit it. At least one of them has to get it right or none of them get to eat cake.
What strategy should they use so that they'll get to eat cake?
Assume the rules are perfectly fair. There is no social trick. They cannot communicate with each other with their hats on. They can't act as mirrors for each other.
Hint 1
When they're told about this game ahead of time and asked to agree on a strategy ahead of being blindfolded in the beginning, what should the strategy be?
Hint 2
Solve for 2 people first.
Be advised:
This is not a simple puzzle. It's a very sophisticated math problem. And very difficult to solve for seven participants. Try to solve for fewer participants (2, 3 then 4) first. Also be strongly advised that Microsoft, Google, Amazon and Facebook are eliminating these teaser problems in their interview process. These kinds of questions have not been highly co-related with on-the-job abilities. Instead, all major companies are adopting purely algorithms and coding questions with full force.
Evaluation
- You solved it for two people (25%)
- You solved it for three people (25%)
- You'd probably eat cake (25%)
- If instead of a party, this was an actual prison, you'd keep your head (25%)
References
Davoud Shirazi asked me this question. He encountered it in an interview with Google.
