Answer to March 24, 2003 Problem

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