18
$\begingroup$

Person A thinks of a 5 digit binary number. Person B tries to guess the number. B can guess a 5 digit binary number and A will respond with the number of correct digits (digits in the right place).

What is the maximum number of guesses B will take to know the binary number (assuming he is playing optimally)?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ Can you clarify what you mean by "know the binary number"? Is it satisfactory to know it in your head, or do you require a final guess once you know it? $\endgroup$ – dpwilson Nov 12 '15 at 14:41
  • 1
    $\begingroup$ Is B optimizing for the maximum-possible-number-of-required-guesses? Or for average-number-of-required-guesses? I think the strategy is a bit different for each (since in the latter case there's more of a penalty for guesses that give you some information but can't themselves be correct). $\endgroup$ – ruakh Nov 12 '15 at 18:06
  • $\begingroup$ Define 'optimally'. $\endgroup$ – Bob Jarvis - Reinstate Monica Nov 12 '15 at 18:15
  • $\begingroup$ Couldn't you just ask for the minimum number of guesses B will take? $\endgroup$ – tfitzger Nov 12 '15 at 20:06
  • 2
    $\begingroup$ I thought technically it should be called a 5-bit binary number, and digit is reserved to base-10. But apparently I was wrong. Anyway, this is very much related to Mastermind game! =D $\endgroup$ – justhalf Nov 13 '15 at 8:44
18
$\begingroup$

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.

Improve this answer
$\endgroup$
15
$\begingroup$

4 guesses to know the number

So after experimenting with some guessing patterns I came up with this one:

00000, 00011, 00101, 01001
First find out the amount of zeros, then always change two digits like I did. If the next thing A says to you is the previous result +2, both changed digits are correct. If it's the same as the previous result and both changed digits are the same, it's either 10 or 01. If it's the same as the previous result and both changed digits are not the same, it's 00 or 11. If it's -2, both changed digits are wrong

Let's test it out

with the sequence 10101
00000 - A says "2", so B knows that there are 2 zeros in the sequence.
00011 - A says "2", so B knows that the last two digits are either 10 or 01
00101 - A says "4", so B knows that the last three digits are 101
01001 - A says "2", so B knows that the second digit is not 1.
B knows the solution! If the last three digits are 101, the second digit is not 1 and there are 2 zeros in the sequence, it can just be 10101! This works with any 5 digit binary sequence

Another example

with the number 11001
00000 - A says "2", so B knows that there are 2 zeros in the sequence
00011 - A says "2", so B knows that the last two digits are either 10 or 01
00101 - A says "2", so B knows that the third->fourth digits are either 11 or 00
01001 - a says "4", so B knows that the second->third digits are 10. That means that the fourth digit must be 0, since the combination of 11 for the third->fourth digits isn't possible anymore. (B knows that the third digit is 0). As a consequence, the last digit must be 1, since the combination 10 for the last two digits isn't possible anymore (B knows that the fourth digits is 0). B also knows that there are only two zeros in this sequence, so the first digit must be 1.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Could you give an example with another number, like 11001? $\endgroup$ – JonTheMon Nov 12 '15 at 15:13
  • $\begingroup$ This strategy checks out for 2's. For 1's though I found you'd have to use the 2's strategy so you eliminate choices faster. Meaning you change 2 numbers at a time instead of 1. $\endgroup$ – Luminous Nov 12 '15 at 15:29
  • $\begingroup$ @JonTheMon See my edit of the 2nd spoiler block, my explanation was wrong initially (I hope it is correct now). Also updated with an example using the sequence you requested. $\endgroup$ – user14478 Nov 12 '15 at 15:37
  • $\begingroup$ Since there's only 32 possible answers, it would be easy to brute force this to see if it worked for all of them. Is this generalizable into $n-1$ or $floor(n/2)$? $\endgroup$ – corsiKa Nov 12 '15 at 16:30
  • $\begingroup$ Let A's response to the all-zeros guess be $z$. If A's response to any of the other guesses differs from $z$, it must differ by 2 correct digits, and the sign of the difference tells us the correct values of those digits. From there, the solution is straightforward. If A reponds $z$ to all guesses, then the $3$ center bits have equal values and the final bit has the opposite. If $z \ge 3$, the center bits are all $1$, and the rest is straightforward. Otherwise, the center bits are all $0$, and the rest is straightforward. $\endgroup$ – user2357112 supports Monica Nov 12 '15 at 22:35
6
$\begingroup$

6. Start with all 0's (or 1's) and flip each bit. If the number of corrects increases, keep that bit the same, if not flip it back, and flip the next bit. If you're lucky the 5th bit was already correct which means it only took 5 guesses, but if you're still wrong on the 6th guess you know you have it.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The question is how long to know the answer and not how long to guess it so your answer is really 5. $\endgroup$ – Engineer Toast Nov 12 '15 at 14:40
  • $\begingroup$ @EngineerToast Nope it's 4 $\endgroup$ – ghosts_in_the_code Nov 13 '15 at 4:04
5
$\begingroup$

First guess:

5

Because:

If you start with 00000 and change one digit at a time. For example, let's say the number is 10010. You guess 00000 and get that 3 digits are correct. Then guess 10000 and get that 4 digits are correct, so now you know that the first digit is correct as 1. Then change it to 11000 and get that 3 digits are correct, so you know the second digit was correct as 0. Then guess 10100 and get that 3 digits are correct, so you know the third digit is 0. Your final guess is on the fourth digit because when you guess 10010 either all 5 digits will be correct or only 3 digits will be correct. If all 5 are correct, then you are clearly done, but if 3 are correct, you can deduce that the fourth digit was right as a 0 and the last digit has to be a 1. You will know the correct answer after 5 guesses. It will take a sixth guess if you need to "guess" it.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Wouldn't this still require a sixth "guess" just to state you have the answer? Even if you know it in your head, you have to put forth a guess. $\endgroup$ – dpwilson Nov 12 '15 at 14:38
  • $\begingroup$ @dpwilson yeah I was just reading that through thinking the same thing. $\endgroup$ – MisterEman22 Nov 12 '15 at 14:39
  • 1
    $\begingroup$ The question is how long to know the answer and not how long to guess it. $\endgroup$ – Engineer Toast Nov 12 '15 at 14:40
  • $\begingroup$ Ok that's what I was thinking when I wrote it before. Thanks @EngineerToast $\endgroup$ – MisterEman22 Nov 12 '15 at 14:41
  • $\begingroup$ Yeah, I guess the question does state "know". I was operating under the assumption that this plays out like Mastermind. $\endgroup$ – dpwilson Nov 12 '15 at 14:42
1
$\begingroup$

If this puzzle is to be evaluated like Mastermind (where a final "guess" is required to confirm the correct solution) then the answer is six, otherwise it is five - using the following approach:

First guess: all 0s (or all 1s). The response to this (number of correct digits) will indicate how many of each digit are used: 0 or 5 - all digits are the same (trivial); 1 or 4 - all digits but one are the same; 2 or 3 - 2 of one, 3 of the other.

Then:

1 or 4 - 2nd guess: aaabb (where a is the more common number). If the response is 4 then one of the b digits is correct - so third guess would be aaaba, and then a fourth guess (if necessary) would be aaaab; otherwise (ie. response is 3) then neither of the b digits is correct - so third guess would be abbaa;

and

If response to third guess is also 3, then number must be baaaa (4th guess), otherwise, fourth guess would be abaaa, and then a fifth guess (if necessary) would be aabaa.

Or

2 or 3 - 2nd guess: aaaab (where a is the more common number).

If

response is 4 then one of the b digits is the last, so third guess would be aabba; if this gave a response of 4 then a fourth guess would be aabab and a fifth guess (if necessary) would be aaabb, otherwise (ie. a response of 3) then a fourth guess would be baaab and a fifth guess (if necessary) would be abaab.

But if

response is 3 then neither of the b digits is the last so third guess would be aabba; if this gave a response of 3 then the fourth guess would have to be bbaaa, otherwise (ie. a response of 4) then a fourth guess would be aabaa;if this gave a response of 4 then one of the b digits would have to be in the third position, otherwise it would have to be in the fourth position; so the fifth guess would be babaa (or baaba), and if necessary the sixth guess would have to be abbaa (or ababa).

Therefore, the worst case scenario would be six guesses as the minimum necessary to determine the combination in any case.

Improve this answer
$\endgroup$
0
$\begingroup$

There are $2^5=32$ possible answers, and each time you ask you get one of 6 responses, so in theory it could be settle in two questions. But I doubt this is possible

Improve this answer
$\endgroup$
3
  • $\begingroup$ You are not answering the question that was asked. $\endgroup$ – Dave Nov 12 '15 at 16:38
  • 2
    $\begingroup$ @dave: Yes it is -- the other answers each produce an upper bound for the question asked, and this answer produces a lower bound. $\endgroup$ – Tyler Seacrest Nov 12 '15 at 20:04
  • $\begingroup$ @TylerSeacrest Gamow has proved both the upper and lower bounds to be 4. $\endgroup$ – ghosts_in_the_code Nov 13 '15 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.