Skip to main content
1 of 2

Mapping problem reminiscent of Mastermind

Given 2 finite sets S and M, with card(S) >= card(M), and an item z not in M. There is an unknown function f: S --> M u {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) != z). The goal is to find f. To this end, I can query an oracle by sending it a question Q subset of S, and getting back from it answer A = f(Q) subset of M u {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?