Solving static permutation mastermind using \(O(n \log n)\) queries (Q2073315)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving static permutation mastermind using \(O(n \log n)\) queries |
scientific article |
Statements
Solving static permutation mastermind using \(O(n \log n)\) queries (English)
0 references
1 February 2022
0 references
Summary: Permutation mastermind is a version of the classical mastermind game in which the number of positions \(n\) is equal to the number of colors \(k\), and repetition of colors is not allowed, neither in the codeword nor in the queries. In this paper we solve the main open question from \textit{C. Glazik} et al. [Discrete Math. 344, No. 3, Article ID 112253, 13 p. (2021; Zbl 1457.91114)], who asked whether their bound of \(O(n^{1.525})\) for the static version can be improved to \(O(n \log n)\), which would be best possible. By using a simple probabilistic argument we show that this is indeed the case.
0 references