2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Oct 20 '16 at 22:01
  • $\begingroup$ Yes, we can (as in example with one bit). But set of static questions is interesting too. $\endgroup$ – Виталий Демиденко Oct 20 '16 at 22:11
  • $\begingroup$ I think this can be solved in $\Theta(n/\log n)$ queries. This paper seems relevant $\endgroup$ – adrianN Oct 21 '16 at 13:20
1
$\begingroup$

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.

$\endgroup$

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.