High / Low Guessing Game
|
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
To locate a number between one and one billion requires only thirty questions,
since
|
possibilities, two questions
leave 
possibilities,
and twenty questions
leave 
possibilities.
The final number of
possibilities is less than one, so the number is determined.
is less than one.
