Given 2 finite sets $S$ and $M$, with $\operatorname{card}(S) \geq \operatorname{card}(M)$, and an item $z \not\in M$. There is an unknown function $f: S \to M \cup \{z\}$, which is known to be one-to-one for all $s \in S$ for which $f(s) \in M$ (i.e. for which $f(s) \neq z$). The goal is to find $f$. To this end, I can query an oracle by sending it a question $Q \subseteq S$, and getting back from it answer $A = f(Q) \subseteq M \cup \{z\}$. Obviously, I could use the trivial strategy and sequentially ask the questions $Q = \{s\}$ over all $s \in S$, but querying the oracle is very costly. Is there a questioning strategy that is less costly than the trivial one? Or can one prove that there is no strategy less costly than the trivial one?



Mapping problem reminiscent of Mastermind
Since $S$ is finite, we can label its elements $s\_1, s\_2, \ldots, s\_n$. Then take as query sets $S\_1 = \{ s\_i \mid i \,\&\, 1 = 1 \}$ where $\&$ represents bitwise conjunction; $S\_2 = \{ s\_i \mid i \,\&\, 2 = 2 \}$, $S\_k = \{ s\_i \mid i \,\&\, 2^{k-1} = 2^{k-1} \}$. This gives $\lceil \lg \operatorname{card}(S) \rceil$ queries. Then the element of $S$ which maps to $m \in M$ can be found by taking the bitwise disjunction of the powers of 2 from the queries whose answers contained $m$.


