Finding out a set by intersection comparison The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related. 

The general setting is the following. We are given $F$, a family of $t$-subsets of $\{1, 2, ..., n\}$, for some parameter $t$ (I am most interested in the case where $t=\lfloor n/2\rfloor$). There is an adversary who picks one set in $F$, denoted by $S$. Our job is to find what $S$ is. To do this, we are allowed to send any two sets in $F$ to the adversary, say $A$ and $B$ and the adversary will output $A$ if $|A\cap S|\geq |B\cap S|$ and $B$ if $|B\cap S|\geq |A\cap S|$. Note that if $|A\cap S|=|B\cap S|$ then the adversary can output either $A$ or $B$. 

This problem can be solved trivially if we do not care how many queries we can ask since if we compare all pairs of sets, $S$ will be the only set that is always returned back from the adversary when we send a query $(S, B)$, for any $B\neq S$. However, our goal is to minimize the number of queries. 

My goal is to show either that this problem can be solved using $O(poly(n))$ queries or that super-polynomial number of queries are required. I'm particularly interested in the case where $F$ is the set of all $\lfloor n/2\rfloor$-subsets of $\{1, ..., n\}$.

Any pointers to anything related would be appreciated.
This is a variation of the famous puzzle of finding a counterfeit coin by using the balance.  But before proceeding to that, first let’s solve the question, because the technique in solving it is also useful to see the connection to the counterfeit coin problem.

First, suppose that the query sets A and B do not have to be from the family F.  Then you can find the set S by at most $\binom{n}{2}=O(n^2)$ queries as follows.  Make $\binom{n}{2}$ queries ({a}, {b}) for 1≤a&lt;b≤n.  Note that every element i∈{1,…,n} is used in n−1 queries.  If an element i belongs to S, then the set {i} is answered at least when the opponent does not belong to S, and therefore the set {i} is answered at least n−t times.  If an element i does not belong to S, then the set {i} cannot be answered if the opponent belongs to S, and therefore the set {i} is answered at most n−t−1 times.  Therefore, counting how many times each set is answered, we can determine the whole set S.

This requires query sets not from the family F, which is not allowed in the problem.  But we can work around this by adding the same t−1 elements to both sides.  For example, instead of making the query ({1}, {2}), we can make the query ({1,3,4,…,t+1}, {2,3,4,…,t+1}).  Therefore, the problem can be solved by O(n2) queries.

Now fun part begins.  Consider n coins labeled 1,…,n, and t of them are counterfeits and slightly heavier than the real coins.  All the counterfeit coins have the same weights.  You have to find the set S of the labels of the t counterfeit coins by using a balance only poly(n) times.  Every time you use a balance, you can put at most min{t, n−t} coins to each side of the balance.  The balance is slightly inaccurate in the sense that if the two sides have the same weight, either side can go down (adversarially).  As I hope that you can see by now, this is exactly the same problem as the question.

Edit: Revision 4 and earlier had one error or another (oops) in the precise connection to the counterfeit coin puzzle.