2016/07/15 by Berger, Aaron, Chute, Christopher, Stone, Matthew
#68Q25 #91A46 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1607.04597
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called codemaker constructs a hidden sequence H = (h1, h2, …, hn) of colors selected from an alphabet A = \1,2,…, k\ (i.e., hi\inA for all i∈\1,2,…, n\). The game then proceeds in turns, each of which consists of two parts: in turn t, the second player (the codebreaker) first submits a query sequence Qt = (q1, q2, …, qn) with qi∈ A for all i, and second receives feedback Δ(Qt, H), where Δ is some agreed-upon function of distance between two sequences with n components. The game terminates when Qt = H, and the codebreaker seeks to end the game in as few turns as possible. Throughout we let f(n,k) denote the smallest integer such that the codebreaker can determine any H in f(n,k) turns. We prove three main results: First, when H is known to be a permutation of \1,2,…, n\, we prove that f(n, n)≥ n - loglog n for all sufficiently large n. Second, we show that Knuth's Minimax algorithm identifies any H in at most nk queries. Third, when feedback is not received until all queries have been submitted, we show that f(n,k)=Ω(nlog k).