The most transparent solution to the problem asks the following questions:

Question 1: When you write your number in base two, is the ones digit a 1?
Question 2: When you write your number in base two, is the twos digit a 1?
Question 3: When you write your number in base two, is the fours digit a 1?
Question 4: When you write your number in base two, is the eights digit a 1?

For numbers in the range of 1 to 10, this is the same as asking:

Question 1: Is your number in the set {1,3,5,7,9}?
Question 2: Is your number in the set {2,3,6,7,10}?
Question 3: Is your number in the set {4,5,6,7}?
Question 4: Is your number in the set {8,9,10}?

Many variations on the above were received.

We received 29 correct answers, several with multiple solutions. Nearly all the solutions were different from one another. The winning entry included an excellent analysis of the number of maximum possible number of solutions. It goes as follows:

First note that four questions is indeed the smallest number of questions with which can find the number, since three Yes/No questions will only distinguish between 2³ = 8 possibilities. The second interpretation of the questions shows that what I'm looking for are four sets of numbers between 1 and 10, and questions of the form: Is your number in the given set. (Note that asking whether your number is in the set gives me the same information as asking whether your number is in the complement of the set, the complement of a set being the elements not in the set.) In order to be able to find your number, the intersection of any four of the sets, or their complements, must have no more than one element in it. Basic set theory shows that a set with 10 elements has 2¹⁰ = 1024 subsets. Some of these subsets are not useful in the questions, for instance we can safely ignore the empty set (and its complement), but also any subsets with only one element (and their complements) since otherwise we would have to distinguish among the other nine elements with only three questions, which is not possible. That leaves
2¹⁰ - 22 = 1002 subsets. These can be divided into pairs -- the sets and their complements -- leaving 1002/2 = 501 pairs of sets to choose from. Now we choose four such sets giving the upper bound of ₅₀₁C₄ which is approximately 1.594 X 10⁹ possible solutions. Of course, not all of these are valid, but it is a pretty reasonable first stab at an upper bound.

Go to the Bradley University Home Page