0
$\begingroup$

The following game is a modified version of the popular game Mastermind described here in which you are only given information about the total correct guesses you have made, and nothing about how many correct digits in wrong place you have. The game goes as follows

Player one starts the game by secretly selecting a sequence of the numbers $\{1,2,\ldots,n\}$ without duplicates. We'll call this sequence $a_1,a_2,\ldots, a_n$.

Player two then at every turn chooses a sequence of numbers $b_1,b_2,\ldots,b_n$, upon which Player 1 will inform them solely of the number of values $1\leq j\leq n$ such that $a_j=b_j$. Player 2's goal is to guess the correct sequence in the minimum number of possible turns.

Question: What is the smallest number of turns that it can take Player 2 to determine the sequence of Player 1's secret configuration?

Clearly Player 2 can just guess each individual number's placement one at a time, which would lead us to the scale of $O(n^2)$ guesses required, however it seems as if there is a better strategy that can take advantage of the knowledge of incorrect as well as correct placements.

Improve this question
$\endgroup$
4
  • $\begingroup$ You can do $n+1$ guesses by $1,2,...,n$, then $2,3,...,n,1$, and so on, and then you will know all values. $\endgroup$
    – Daniel Weber
    Commented Feb 20 at 2:32
  • $\begingroup$ Wait, does he get the number of matches or the indices? $\endgroup$
    – Daniel Weber
    Commented Feb 20 at 2:43
  • 1
    $\begingroup$ If he gets the number then see, for example, the paper Playing Mastermind with Many Colors which shows an upper bound of $O(n\log\log n)$, and as far as I know it's the best known $\endgroup$
    – Daniel Weber
    Commented Feb 20 at 2:47
  • 1
    $\begingroup$ @CommandMaster Player 2 knows the number of matches, not the indices $\endgroup$
    – YCor
    Commented Feb 20 at 8:01

0

Reset to default

You must log in to answer this question.