Finding superset of chosen set Mary and Neal play a game. Let $n$ be a perfect square. Neal chooses a subset of size $\sqrt{n}$ from a set of size $n$. Each turn, Mary can choose a subset of any size, and Neal has to say whether the subset contains the subset of size $\sqrt{n}$ that Neal chose. After a polynomial number (in $n$) of such exchanges, Mary has to guess Neal's subset. If she does so, she wins.
Under optimal strategy, can Mary have a probability of at least $1/poly(n)$ of winning the game? 
If she asks Neal randomly about subsets of size $\sqrt{n}$, there are $\binom{n}{\sqrt{n}}$ subsets of size $\sqrt{n}$, so the chances that she finds Neal's subset within a polynomial number of exchanges is exponentially low. Maybe she can ask on subsets of greater size, but this shouldn't help either. The question is how this can be made into a formal argument.
 A: Mary can identify the set with certainty in $O(n)$ rounds, thus polynomial.
The strategy is as follows:


*

*The aim is to find which elements of $F$ are elements of $N$. At round $k$ there will be three sets that partition $F$:


*

*The set $M_\checkmark^{(k)}$ of elements of $F$ identified as part of $N$ at round $k$. Clearly, $M_\checkmark^{(k)}\subset N$.

*The set $M_\times^{(k)}$ of elements of $F$ identified as not part of $N$ at round $k$. Clearly, $M_\times^{(k)}\subset(F\setminus M)$.

*The set $M_?^{(k)}$ of elements of $F$ for which it is not yet known at round $k$ whether they are element of $N$. Clearly, $N\subset (M_?^{(k)}\cup M_\checkmark^{(k)})$.


*Initially, obviously $M_?^{(0)}=F$, $M_\checkmark^{(0)} = M_\times^{(0)} = \emptyset$.

*Now Mary iterates the following algorithm:


*

*Obviously, if $M_?^{(k)}$ is empty, the process has finished, and $F=M_\checkmark^{(k)}$.

*Otherwise, Mary selects one element $x_k$ from $M_?^{(k)}$ and asks for the set $M_k := M_\checkmark^{(k)}\cup M_?^{(k)}\setminus\{x_k\}$

*Mary updates her sets according to Neal's answer.


*

*If Neal answers that $N\subset M_k$, then Mary knows that $x_n\notin N$, therefore $M_?^{(k+1)} = M_?^{(k)}\setminus\{x_k\}$, $F_\checkmark^{(k+1)} = M_\checkmark^{(k)}$, $M_\times^{(k+1)} = M_\times^{(k)}\cup\{x_k\}$.

*If Neal answers that $N\not\subset M_k$, then Mary knows that $x_n\in N$, therefore $M_?^{(k+1)} = M_?^{(k)}\setminus\{x_k\}$, $F_\checkmark^{(k+1)} = M_\checkmark^{(k)}\cup\{x_k\}$, $M_\times^{(k+1)} = M_\times^{(k)}$.


*Mary starts the next iteration.



Obviously $M_?^{(k+1)}$ always has one element less than $M_?^{(k)}$. Since $M_?^{(0)}=F$ has exactly $n$ elements, $M_?^{(n)}=\emptyset$ and the algorithm ends after exactly $n$ rounds.
Note that the end condition could be changed to "$M_?^{(k)}\cup M_\checkmark^{(k)}$ has exactly $\sqrt{n}$ elements". That is, as soon as you have identified all elements not in $N$, you're obviously finished.
But the algorithm as given above suffices to prove that it takes only a polynomial (indeed, linear) time to identify the subset with certainty.
