The exact query complexity of yes-no permutation mastermind (Q2221264)

Summary: Mastermind is famous two-player game. The first player (\textit{codemaker}) chooses a secret code which the second player (\textit{codebreaker}) is supposed to crack within a minimum number of code guesses (queries). Therefore, the codemaker's duty is to help the codebreaker by providing a well-defined error measure between the secret code and the guessed code after each query. We consider a variant, called Yes-No AB-Mastermind, where both secret code and queries must be repetition-free and the provided information by the codemaker only indicates if a query contains any correct position at all. For this Mastermind version with \(n\) positions and \(k \geq n\) colors and \(\ell := k+1-n\), we prove a lower bound of \(\sum_{j=\ell}^k \log_2 j\) and an upper bound of \(n \log_2 n + k\) on the number of queries necessary to break the secret code. For the important case \(k=n\), where both secret code and queries represent permutations, our results imply an exact asymptotic complexity of \(\Theta (n\log n)\) queries.