We first present a complete description and analysis of an approach that
takes
4 guesses to know the correct number.
Furthermore, we will show that with fewer guesses one cannot guarantee success.
Description and analysis of the algorithm
With a first guess 00000, the six possible answers are as follows:
- Score 0: Then the hidden number is 11111. Done.
- Score 1: Then we succeed with a total of four guesses (see Case A below).
- Score 2: Then we succeed with a total of four guesses (see Case B below).
- Score 3: This case is symmetric to Case B.
- Score 4: This case is symmetric to Case A.
- Score 5: Then the hidden number is 00000. Done.
Case A: The guess 00000 has a score of 1.
The hidden number consists of four 1s and a single 0. Our second guess is 00111.
- If the score is 4, we know that the hidden number is 01111 or 10111.
We succeed with one additional guess.
- If the score is 2, we know that the hidden number is 11011, 11101 or 11110.
We succeed with two additonal guesses.
Altogether, this yields at most four guesses in case A.
Case B: The guess 00000 has a score of 2.
The hidden number consists of three 1s and two 0s. We guess 11000.
Let us distinguish three situations on the first two positions of the hidden number.
- If the hidden number is 11xxx, then the score of 11000 equals 4.
- If the hidden number is 10xxx or 01xxx, then the score of 11000 equals 2.
- If the hidden number is 00xxx, then the score of 11000 equals 0.
This implies the following:
- If the score of 11000 is 0, we know that the hidden number is 00111. Done.
- If the score of 11000 is 4, we know that the hidden number is 11100, 11010 or 11001. We succeed with two additonal guesses.
- If the score of 11000 is 2, we know that the hidden number starts with 10 or 01, and ends with 011 or 101 or 110. This is the only remaining case (***).
In this only remaining case (***), our third and fourth guesses are 01011 and 01101. This yields the scores in the following table:
| 10011 10101 10110 01011 01101 01110
---------------------------------------------------------
guess 01011: | 3 1 1 5 3 3
guess 01101: | 1 3 1 3 5 3
We see that every column occurs only once, and hence allows us to correctly
identify the hidden number.
Altogether, this yields at most four guesses in each of the subcases of case B.
Lower bound argument:
Independently of the structure of the first guess, player A announces a score of 2. This then leaves player B with exactly 10 possible numbers (as the hidden number must agree with the guess in two places and disagree in the other three places).
Here is the crucial observation: whenever player B announces his guess from now on, then the parity (odd/even) of the answer of A is already pre-determined.
Hence the spectrum of possible answers is either $\{0,2,4\}$ or $\{1,3,5\}$.
By using two more guesses, this only yields nine distinct possibilities for the answers, and this is not enough to distinguish between ten possible cases. Therefore three guesses are not enough.