Finding superset of chosen set

Question

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.

Answer 1

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:
  1. Obviously, if $M_?^{(k)}$ is empty, the process has finished, and $F=M_\checkmark^{(k)}$.
  2. 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\}$
  3. 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)}$.
  4. 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.