# Find number X by asking Hamming distance between X and Y in binary representation

We need to find unknown 16-bit integer X. We can ask "how many '1'-bits in number X xor Y" (Y is 16-bit too). What best strategy to find X? Or what minimum number of questions?

For example, if answer for Y=0 is 1, we can do binarysearch-like strategy restoring X in 4 additional operations.

I have found set of 10 numbers {26330, 15436, 4730, 5006, 10083, 227, 2775, 2367, 17754, 25121} such if we ask about all of these, we can uniquely restore X.

• 1. Are we allowed to choose queries adaptively? In other words, are we allowed to pick the next query $Y$ based on the set of all answers to all prior queries? Or do we have to specify the list of all queries $Y$ in advance, before seeing the answers to any of them? 2. Relevant (but not identical): en.wikipedia.org/wiki/Mastermind_(board_game). See especially Knuth's algorithm. – D.W. Oct 20 '16 at 22:01
• Yes, we can (as in example with one bit). But set of static questions is interesting too. – Виталий Демиденко Oct 20 '16 at 22:11
• I think this can be solved in $\Theta(n/\log n)$ queries. This paper seems relevant – adrianN Oct 21 '16 at 13:20

One reasonable heuristic would be to use a greedy algorithm, which at each step picks a query that is likely to reduce the space of possibilities as much as possible.

Suppose you care about the maximum number of questions (worst-case). Then I suggest the following strategy. At any point, you have a set $S$ of possible values of $X$ that remain. For each possible query $Y$ and each possible response $R$ to that query, let $n(Y,R)$ denote how many possibilities of $S$ would remain consistent with the response $R$ to query $Y$. Define $n(Y) = \max_R n(Y,R)$. Now, choose the query $Y$ that makes $n(Y)$ as small as possible. [This is basically Knuth's minimax algorithm.]

Alternatively, suppose you care about the expected number of questions asked (average-case). Then do the same, except now define $h(Y)$ to be the entropy of a random variable that takes on the value $R$ with probability $n(Y,R) / |S|$. In other words, define

$$h(Y) = - \sum_R {n(Y,R) \over |S|} \lg {n(Y,R) \over |S|}.$$

Then choose the query $Y$ that minimizes $h(Y)$.

There is no guarantee that these procedures are optimal, but I bet they're pretty good.

Related but not the same: you might also be interested in Ulam's game, a generalization of the game of 20 questions. Also, take a look at this post, which describes an algorithm for 20 questions based on entropy calculations.