zbMATH — the first resource for mathematics

Playing Mastermind with constant-size memory. (English) Zbl 1245.68144
Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 441-452, electronic only (2012).
Summary: We analyze the classic board game of Mastermind with \(n\) holes and a constant number of colors. The classic result of V. Chvátal [Combinatorica 3, 325–329 (1983; Zbl 0717.05002)] states that the codebreaker can find the secret code with \(\varTheta(n / \log n)\) questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of S. Droste, T. Jansen and I. Wegener [Theory Comput. Syst. 39, No. 4, 525–544 (2006; Zbl 1103.68115)] on the memory-restricted black-box complexity of the OneMax function class.
For the entire collection see [Zbl 1237.68016].

68R05 Combinatorics in computer science
91A05 2-person games
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI