combinatorics – Complex query to identify a subset

Fix an ambient finished set $ X $without loss of generality $ X = {1, ldots, | X | } $. You want to identify a subset $ B subseteq X $ hidden to you. You can get information about the subset as follows: you can choose any subset. $ C subseteq X $and you receive the number $ | B cap C | $.

In terms of $ | X | $ (and eventually $ | B | $), what is the minimum number of queries needed to determine $ B $? How about a particular case, for example when $ | B | leq log_2 (| X |) $?


Some observations:

  • L & # 39; s case $ | B | = $ 1 allows for binary search, and so can be done in $ lceil log_2 (| X |) rceil $. Already for $ | B | = $ 2, a way with less $ 2 log_2 (| X |) + C $ queries are not clear to me (although I can see how to do $ frac32 log_2 (| X |) + C $ on average).
  • trivially $ | X | $ queries are always enough: just start with $ C = X $ and delete an item for each query.
  • This question was inspired by a recent Google Code Jam problem: your query consists of one bit for each element of $ X $and you get $ | X | – | B | $ bits back. However, in the Google Code Jam problem, the returned bits are always sorted correctly, but with the missing values. This allows you to match responses from multiple queries. then $ lfloor log_2 (| B |) + 1 rfloor $ the requests are sufficient.