Draft:Bpow1997-1

I am on a long term scientific mission to the South Pole, In order to keep my spirits up we agree to play a game. I will pick a number between one and 10 (inclusive) and you try to guess it. (Okay, so it's not the greatest of games.) Being a good sport, I allow you to ask me four questions which I will answer either YES or NO. We have trained four carrier penguins to ferry the questions and answers back and forth between the South Pole and Peoria. In order not to tire out the penguins, we agree that each one is to carry only one question and return with the answer to that question. I will answer the questions as soon as I get them. What four questions would you ask?

( Note. Since you don't know which penguin will reach me first, your questions cannot be of the form: If the answer to the first question is YES, then...)

Solution

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 23 = 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 210 = 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

210 - 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 501C4 which is approximately 1.594 X 109 possible solutions. Of course, not all of these are valid, but it is a pretty reasonable first stab at an upper bound.

Problem by Alberto L Delgado, from the now extinct Bradley Problem of the Week.