Each year, I assign my programming classes the task of writing a program
to simulate the following guessing game.
The game requires that one try to determine by means of yes or no
questions an arbitrary number between one and ten million. What is
the minimum number of questions that are necessary in order to
determine any number that is picked?
Solution to Problem:
The answer is 24 questions.
Why do 24 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 5,000,000? - leaves
10,000,000 x (1/2) or 5,000,000 possibilities.
Two questions leave 10,000,000 x (1/2)2
or 2,500,000 possibilities. Twenty-four questions would leave
10,000,000 x (1/2)24 or .596 possibilities. Since that number is less than 1,
it means there is only one possibility.
To locate a number between one and one billion requires only thirty questions, since is less than one.
Correctly solved by:
1. Richard Johnson | La Jolla, California |
2. Keith Mealy | Cincinnati, Ohio |
3. Bill Funk | San Antonio, Texas |
4. James Alarie | University of Michigan -- Flint, Flint, Michigan |
5. Steve Muller | Winchester, Virginia |
6. Matt Stillwagon | Winchester, Virginia |
7. David & Judy Dixon | Bennettsville, South Carolina |
8. Tina Zahel | Winchester, Virginia |
9. Bob Hearn | Winchester, Virginia |
10. Walt Arrison | Philadelphia, Pennsylvania |
11. Jaime Garcia | Winchester, Virginia |
12. Jeff Gaither | Winchester, Virginia |