You and I will play a game that bears a family resemblance to the board game "Mastermind." I think of a five binary-digit secret number, for example, 10101. You are allowed to ask about bit sequences of length five. Such a question is called a "bit question". My responses will report how many bits in your guess have their correct value in the correct place.
For instance, if your bit question is 10110 and my secret is 10101, then three of your bits (the first three, though I won't tell you that) are in the correct place with their correct value. In this case, I could have other secret numbers that are consistent with that answer such as 00100.
Warm-up: In fact, how many numbers would be consistent with the answer of "three correct" for a bit question of 10110?
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Solution to warm-up: There would be 10. (If you know combinatorics, the answer comes from the calculation of "5 choose 3".) They would be:
10101, 10011, 10000, 11111, 11100, 11010, 00111, 00100, 00010, 01110.
There are many systematic ways to generate such a sequence. Mine was to say, "Suppose the first three are correct. Next suppose the last of the first three is incorrect, but the first two of the first three are correct. Next, the second to last of the first three is incorrect, the third of the first three may be incorrect, but the first of the first three is always correct. Then the first of the first three is incorrect and the others may be, too."
Second Warm-up: If you guessed 10110 and were told that all five were incorrect, then which possibilities would there be?
Solution to second warm-up: Only one: 01001. Just reverse all the digits of the question.
Problems:
1. What is the smallest number of bit questions sufficient to always determine a five-bit sequence? Remember that none of the guesses in your bit questions need be correct. You just need to know how to crack the secret of my sequence at the end.
2. What if we change the game to make it harder for you: you ask some number of questions and then I answer them all after you have asked your last one. In that case, how many bit questions are sufficient?
These next questions are more challenging and involve a slight twist in the rules of the game. When you ask your first bit question, you get no answer. After that, each bit question is answered in one of the following three ways:
(i) "You have the same number correct as in the last bit question."
(ii) "You have more correct than in the last bit question."
(iii) "You have fewer correct than in the last bit question."
In these answers, "correct" means correct value in the correct position. We call this type of response the low-info answer.
3. Given only low-info answers to bit question, is it possible to find the secret number, no matter what it is? If so, how many bit questions (counting the initial one) do you need to guarantee to find the secret number, assuming the answers to the questions (except the initial one) come after all questions are posed?
4. How many questions do you need in the low-info case, if you get the answers immediately?
5. How many questions do you need in the low-info case, if the code is N bits long and all answers come at the end?
6. How does this solution generalize if the code is N digits long, but the digits could be base b for some b > 2? For example b could be 10 and all digits 0 through 9 would be allowed. I have a solution that requires 1 + (b-1)*N. I don't think it's optimal.
