High / Low Guessing Game
An Explanation by David Pleacher
A familiar game requires that one try to determine by means of yes or no
questions an arbitrary number between one and one million.
Why do twenty questions always suffice for this?
Each question can cut the number of possibilities in half. Thus,
the first question - Is it less than or equal to 500,000? - leaves
possibilities, two questions
leave possibilities,
and twenty questions
leave possibilities.
The final number of
possibilities is less than one, so the number is determined.
To locate a number between one and one billion requires only thirty questions,
since is less than one.