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.
