Halve the guessing range

Logical thinking · Suggested grades 4

Halve the guessing range

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

A secret number is 1–8. At most how many halving questions?