# Mind Games

Image: GARY ZAMCHICK

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?

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.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• Reuters | 2 hours ago

### Six People Rescued from Nevada Cold Kept Warm by Heating Stones

• Reuters | 4 hours ago

### Ex-BP Supervisors Win Dismissal of Some Manslaughter Charges

• Reuters | 6 hours ago

### EPA Tells Court U.S. Mercury, Toxics Rule Is Legally Justified

• Image Gallery | 8 hours ago | 2

### Chelyabinsk Meteor: Dust Grains Reveal How It Played Bumper Car Before Hitting Earth

• News | 10 hours ago | 5

## Latest from SA Blog Network

• ### Blast from the Past: A Few Science Highlights from 1994

Cocktail Party Physics | 8 hours ago
• ### Public Domain Day: January 1st

Compound Eye | 10 hours ago
• ### Air pollution stretches from Beijing to Shanghai, as seen from space

Plugged In | 11 hours ago
• ### Are Genes Really Selfish? [Video]

Observations | 11 hours ago
• ### Conversation on Daydreaming with Jerome L. Singer

MIND
Beautiful Minds | 12 hours ago

## Science Jobs of the Week

Mind Games

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X