Optimal schemes for combinatorial query problems with integer feedback
share
A query game is a pair of a set Q of queries and a set ℱ of functions, or code words f:Q→ℤ. We think of this as a two-player game. One player, Codemaker, picks a hidden code word f∈ℱ. The other player, Codebreaker, then tries to determine f by asking a sequence of queries q∈ Q, after each of which Codemaker must respond with the value f(q). The goal of Codebreaker is to achieve this using as few queries as possible. Two classical examples of such games are coin-weighing with a spring scale, and Mastermind, which are of interest both as recreational games and for their connection to information theory. In this paper, we will present a general framework for finding short solutions to query games. As applications, we give new self-contained proofs of the query complexity of variations of the coin-weighing problems, and prove new results that the deterministic query complexity of Mastermind is Θ(n log k/ log n + k) if only black-peg information is provided, and Θ(n log k / log n + k/n) if both black- and white-peg information is provided. In the deterministic setting, these are the first up to constant factor optimal solutions to Mastermind known for any k≥ n^1-o(1).
READ FULL TEXT