March 24, 2003
Problem of the Month

The High / Low Game

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 the 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)² or 2,500,000 possibilities. Twenty-four questions would leave 10,000,000 x (1/2)²⁴ 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

Send any comments or questions to: David Pleacher