Puzzle | Guess the bit string

Puzzle: Your friend thinks of an N bit string that will refer to it as a code. The task is to guess the code by asking your friend a series of queries. In each query, you can provide your friend with an N bit string of your choice, and your friend will tell you the number of bits in your string that coincides with the corresponding bits in the code. For example, if the code is 01011 and your query string is 11001, then the answer will be three because the two strings have the same bits on the second, third, and fifth positions. Devise an algorithm that can identify any N bit code in no more than N query.

Solution:

• Let the N bit binary code string be b₁b₂….b_n, it can be identified using the following N queries:

  Query 1 – 000…00
  Query 2 – 100…00
  Query 3 – 110…00
  ………………
  ………………
  ………………
  Query N – 11….10

• The answer to the first query a₁, gives the total number of 0s in the code string being identified. Let a₂ be the result to the second question.
• Since the query bit strings in the first two questions differs only by one bit, hence, the number of correct bits in them will also differ by one, that will help to identify the first bit b₁ of the code for us as follows:
  • If a₁ < a₂, b₁ = 1
  • If a₁ > a₂, b₁ = 0

  For example, for code 01011, a1 = 2 and a2 = 1, therefore b1 = 0.

• Repeating the same argument for the next N – 2 bits of the string makes it possible to identify the bits, b₂, …, b_{N – 1} of the code.
• The last bit b_N can be found by using the total number of 0s in the code determined by the first query: if this number is equal to the number of zeroes in the code’s first N – 1 bits, which are now known, then bn = 1, else bn = 0.

Example: Let N = 3 and the code which your friend thought be “110”.
The code can be guessed in 3 queries.

1. Query 1 = “000”: The answer to the query is 1 as only the third-bit matches in the string “110” and “000”. The resultant code bit string has a total of 1 zero.
2. Query 2 = “100”: The answer to the query is 2 as only two-bit matches in the string “100” and “110”. Since in this query changing only the first bit from the last query and the resultant code bit increased so the first bit of code string will be ‘1’.
3. Query 3 = “110”: The answer to the query is as since three-bit matches. So now since we changed only the first bit from the last query and the answer increased so the second bit of code string will be ‘1’.

From the above, we know that two of the bits are ‘1’. And we have 1 zero in the code string so the third bit will be a ‘0’. Therefore, code string = “110”