Mind Games

Mind Games

You and I play a game that bears a strong family resemblance to the board game Mastermind. I think of a five binary digit secret number, e.g., 10101. You are allowed to pose questions 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 example, 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. On the other hand, I could have other secret numbers that are consistent with the three-are-correct answer such as 00100.

Warm-Up

In fact, how many would be consistent with the answer of three correct for a bit question of 10110?

Solution to Warm-Up

Ten answers would be consistent. They would be: 10101, 10011, 10000, 11111, 11100, 11010, 00111, 00100, 00010, and 01110.

Warm-Up 2

If you guessed 10110 and were told that all five were incorrect, then which possibilities would there be?

Solution to Warm-Up 2

Only one sequence is consistent with that answer: 01001. Just reverse all the bits.

Warm-Up 3

If I give you the following answers, what is the secret number?

• 00000 - 2 correct

• 01000 - 1 correct, so second bit must be 0

• 00100 - 3 correct, so you know x01xx

• 01110 - 3 correct, so x011x

• 11100 - 1 correct, so 0011x

• 00001 - 3 correct, so last bit is 1 (compare with first response)

Solution to Warm-Up 3

Therefore, the secret number is 00111. These questions don’t follow any particular systematic procedure, however. We should be able to do better.

1. What is the smallest number of bit questions sufficient to determine a five-bit sequence, no matter what it is? Remember that none of your bit questions need be correct. You just need to know how to crack the secret at the end.

Hint: 

A five question solution is not too hard to find, so try that first. You can do better, however.

2. Suppose we change the game to make it a little more difficult: You ask some number of questions and then I answer them all after you have asked all your questions. In that case, how many bit questions are sufficient?

I’ve become decidedly less friendly. You pose an initial bit question, to which I give no response at all - ever. As with question 2, I answer all your questions after you have asked the last one. After that, I give you only “low info” answers, consisting of one of three responses:

1. You have the same number correct as in the last bit question (S).

2. You have more correct than in the last bit question (+).

3. You have fewer correct than in the last bit question (-).

That’s all I say. The term “correct” here still means correct bit in the correct position.

3. Given that the low info answers come at the end and there is no answer at all to the first bit question, is it possible to find the secret number, no matter what it is? If so, how many bit questions (counting the first one) do you need to pose in order to guarantee finding the secret number?

4. How many bit questions do you need, if you hear the low info answers immediately after posing them?

5. How does this 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 when all answers come at the end, but that requires 1 + (b-1) × N questions. I don’t think it’s optimal.