How do I crack a simple code using permutations?

Question

I was told by my computing professor that if we have a randomly generated n-bit binary string (I'll use $n=9$ for this example) it can always be guessed in 6 or less guesses provided we initially know the amount of 1's and 0's in the number, and after each guess we are told how many bits we guessed in the right position. I understand the permutations would be $9\choose x$ where $x$ is the number of 1's in the string. But with 126 permutations of strings containing 4 1's (or 5 1's) how could this be done in 6 guesses?

Answer 1

I'll show how you can find a randomly generated 9-bit string with 6 guesses or less, if you know that there are four 1 bits and five 0 bits and after each guess you are told how many bits you got right (but not which bits).

You have correctly identified that there are $126$ possible 9-bit strings that contain exactly four 1 bits. You are wondering how we can distinguish between these $126$ possible strings with only 6 guesses. Having 6 guesses does not mean that we can only check 6 random permutations and hope we are lucky. We are getting valuable information after each guess and this can guide our search.

One key observation is that if our guesses contain the correct number of 1s (i.e., four 1 and five 0) then the only possible replies for correctly guessed bits are: $9,7,5,3,1$. This might not be evident at first, but notice that if we change the value for one bit (say $0\rightarrow1$), then we have to change some other bit $1\rightarrow0$ in order to keep the right number of ones and zeros in the string. Another way to think about it, is that we are only allowed to swap bits that have different values (there is no point swapping bits that have the same value, because nothing would change). So if we have all 9 bits correct and do a swap, we will end up with 7 correct bits. If we then swap only one bit that is incorrect, we will again get 7 bits correct. If we swap two correct bits we go down to 5 correct bits, and so on.

I will present a solution where our guesses always contain the correct number of 1s and 0s. This does not mean that other solutions (not following this restriction) do not exist.

A reply of 9 correct bits, means we are done, so we only need to decide what to do when we get an answer of $7,5,3,1$ correct bits. I will break the strategy into cases, according to what is the reply to our first guess. In order to help the discussion, imagine that we have to find the (unknown to us) target string $001111000$. Let's first examine the case when our first guess returns a reply of $1$ correct bit. Perhaps surprisingly, this is the easiest case to handle.

First guess returns 1 correct bit

This means that the single correct bit has to be a 0. So we immediately know that all our 1 bits are incorrect and they have to be changed. I will use specific bit-string examples to describe how we proceed in each case, but this does not take away any of the generality of the solution. In order to easily show our knowledge on the bits after each reply, I will use the following colour code:

• $\color{green}{\text{green}}$ digits are are ones we know are correct (correct value at the correct position),
• $\color{red}{\text{red}}$ digits are the ones we know they are incorrect,
• $\color{orange}{\text{orange}}$ digits are the ones that have only one correct digit among them,
• $\color{blue}{\text{blue}}$ digits are the ones that have only one incorrect digit among them,
• black digits means that we do not have any information about them.

Notice that if we can write a digit in green we can also write it in red (using the opposite value), it is basically equivalent knowledge. Similarly, orange and blue are equivalent (you can go from one to the other by flipping the values of the digits).

I will use these colours to describe the deductions we can make after a reply (including knowledge from previous replies). When writing the guesses I will only use the green colour to denote that we should not care about these digits because we have found them (the rest of the guess will be written in black, even though we might have information on these digits). Finally, I will indicate the bits changed from the previous guess with overlines. For example, if my first guess is $111100000$ and for the second guess I swap the first and last bits I will write: $\overline0 1110000 \overline1$. This makes it easier to follow the moves/guesses.

So let's start with a guess that produces a reply of $1$ and see what we can deduce. Remember that our unknown target is $001111000$

Guess1 $100000111$, reply $1$, $\implies \color{red}1 \color{orange}{00000} \color{red}{111} $

As discussed before, we know all our 1s are incorrect. Also if we know $\color{red}1 \color{orange}{00000} \color{red}{111}$ we equivalently know $\color{green}0 \color{blue}{11111} \color{green}{000}$. This means that we just need to find the single 0 in the five blue digits we have.

Guess2 $\overline{\color{green}0 1111}0\overline{ \color{green}{000}}$, reply $7$, $\implies \color{green}0 \color{blue}{1111}\color{red}0 \color{green}{000}$

Guess3 $\color{green}0 111\overline 0\color{green}{\overline1 000}$, reply $7$, $\implies \color{green}0 \color{blue}{111}\color{red}0 \color{green}{1000}$

Guess4 $\color{green}0 11\overline0 \color{green}{\overline1 1000}$, reply $7$, $\implies \color{green}0 \color{blue}{11}\color{red}0 \color{green}{11000}$

Guess5 $\color{green}0 1\overline0 \color{green}{\overline1 11000}$, reply $7$, $\implies \color{green}0 \color{red}{10} \color{green}{111000}$

Guess6 $\color{green}{0\overline{01}111000}$, reply $9$, Success

So essentially we found four of the five zeros after our first guess, and then we tried to find the single remaining zero among 5 digits (which can take up to 5 more guesses in the worst case)

First guess returns 7 correct bits

Let's see now how we would react when our first guess returns a reply of 7.

Guess1 $000111100$, reply $7$, $\implies \color{blue}{000111100}$ (2 digits are incorrect, but I do not want to use another colour, to avoid an overload)

So we know that we need to find the correct pair to swap. But there are 20 possible pairs (each of the four 1s can be swapped with each of the 5 0s). How can we find the correct one in 5 guesses? Start swapping and you collect information.

Guess2 $\overline1 00 \overline0 11100$, reply $5$, $\implies \color{red}1 \color{blue}{00} \color{red}0 \color{blue}{11100}$ (blue: 2 digits are incorrect)

Guess3 $\color{green}0\overline1 0\color{green}1 \overline0 1100$, reply $5$, $\implies \color{green}0 \color{red}1 \color{blue}{0} \color{green}1 \color{red}0 \color{blue}{1100}$ (blue: 2 digits are incorrect)

Guess4 $\color{green}{00} \overline1 \color{green}{11} \overline0 100$, reply $7$, $\implies \color{green}{00} \color{orange}1 \color{green}{11} \color{orange}0 \color{blue}{100}$ (blue: 1 digit is incorrect)

We know that these two digits are orange (so one is correct and one is incorrect) because they are the only changes compared to Guess1, and the reply is still $7$. So now we should choose to swap again one of them with another digit, and see what the result is. If we are lucky and we get $9$ matches we finish. Or we can get $5$ matches and we know that these two digits are incorrectly swapped which means that we know which is the correct and which the incorrect digit from the previous swap. Finally, we can get $7$ matches again which would mean that we can again figure out the correct and incorrect digits from the previous swap. Let's try the worse case here:

Guess5 $\color{green}{00} \overline0 \color{green}{11} 01 \overline1 0$, reply $5$, $\implies \color{green}{00} \color{red}0 \color{green}{11} \color{red}0 \color{blue}1 \color{red}1 \color{blue}0$ (blue: 1 digit is incorrect)

Because we know there are only 4 1s we know the answer for the blues: both are 0.

Guess6 $\color{green}{00 \overline1 11\overline{100}0}$, reply $9$, Success

First guess returns 5 correct bits

Let's start examining the case when we find 5 matches with our first guess. I will start it but not conclude it, as the answer becomes tedious. I will leave it as an exercise for the OP. The same goes for the case when we find 3 matches with our first guess.

Guess1 $100011100$, reply $5$, $\implies \color{blue}{100011100}$ (4 digits are incorrect)

Again we start by swapping two random bits (that have different values). If our reply is $7$ then we are in the same subcase as previously examined: knowing 2 digits, and having 2 mistakes in the remaining ones. If the reply is $3$ then we are in the subcase where we know 2 digits and there are 4 mistakes in the remaining 7 ( we proceed similarly with the 7 remaining digits). The most challenging subcase here is that we do a swap and we again get a reply of $5$. This means that only one incorrect digit was swapped. For example:

Guess2 $\overline{01}0011100$, reply $5$, $\implies \color{orange}{01}\color{blue}{0011100}$ (blue: 3 digits are incorrect)

So now we choose one of these bits and we swap again with another bit.

Guess3 $0\overline{01}011100$, reply $7$, $\implies \color{green}{001}\color{blue}{011100}$ (blue: 2 digits are incorrect)

I leave the rest of the moves as an exercise.

Other strategies

I thought a bit about how to solve the problem when say we have only one 1 bit in the 9-bit string. Initially I thought that we needed 9 guesses at the worse case. But this happens only if we stick to the restriction that our guesses have to have the correct number of 1 bits in them. When we have only one 1 bit it's better to let go of this restriction and instead do a kind of binary search on the string, by initially setting half of the bits to 1 (rounded to the closest integer) and see how many mistakes we get. This will tell us if the 1 bit is the in the ones we chose, or not. We proceed this way and in at most 5 guesses we have our answer.

I am wondering if your professor provided a general formula for the maximum guesses needed when we have $r$ 1 bits in a $n$-bit string.