Halve the guessing range
Halve the guessing range
The video could not load. Check your connection and try again, or download it directly.
Download video
Open Chinese transcript
- 秘密数只在1到16中。每次问当前范围中点,把候选尽量分成两半。
- 先问是否大于8。无论回答怎样,16个候选都缩成8个。
- 第二次对剩下的8个再折半,最多剩4个;第三次最多剩2个。
- 第四次把最后2个分开,每条回答路径只剩1个数。
- 候选上限依次是16、8、4、2、1,所以最多需要4次。
- 这是对1到16这个有限集合的保证,不延伸成任何情境下都最快的结论。四层回答路径的叶子必须覆盖全部16个候选。
Sources for this explanation
Logical thinking
Build the finite halving decision tree and count its worst-case depth.
Worked example
The secret is 1–16. Ask at the midpoint, first “greater than 8?”, then halve the remaining range. At most how many questions?
Successive halves have at most 8, 4, 2 and 1 candidates, so four yes/no questions cover all 16 possibilities.
Try one question
8→4→2→1 takes 3 questions.