Fewest yes/no questions on average
One of six suspects is guilty, with probabilities . You may ask any yes/no question (for example "is it one of suspects 2, 4 or 5?") and get a truthful answer. Using the strategy that minimises the expected number of questions, what is that expected number?
Show hints (2)+
- Each strategy is a binary tree; the expected number of questions is the average leaf depth.
- Huffman: merge the two smallest probabilities repeatedly and add up the merged weights.
Answer
Reveal answer →Final answer
2.35 (± 0.001)
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading, Systematic & Data-Driven Trading