# permutation search game

Arrange the natural numbers $1$ through $n$ in a random order (the order is unknown and has a uniform distribution). Now make a sequence of guesses as to which number is in which slot, one number and one slot at a time. You will be told after each guess whether it is correct or not. The game ends when the order of the $n$ numbers has been determined. For the worst case and the average case, respectively, is there a strategy that takes fewer guesses than the trivial elimination?

• It seems like due to symmetry, the optimal strategy is random guessing (without guessing numbers that have already been found, of course). Do you have any reason to suspect there's a better strategy? – ferson2020 Mar 5 '13 at 14:22
• @ferson2020: From a mathematical perspective, the interesting question is: Can we prove that there is no better strategy? I can't right away, but it feels like there ought to be some clever amortization argument showing that one may always need to ask $n(n-1)/2$ questions in the worst case -- or perhaps just something $O(n^2)$. – Henning Makholm Mar 5 '13 at 14:26
• Again, I would argue symmetry. At any given stage, you have some permutation of $k < n$ things left, and you have to pick which one is, without loss of generality, in the first position. It would be strange to think that there could be any bias due to any strategy that you should pick one of the items over the others. – ferson2020 Mar 5 '13 at 14:35
• Interestingly enough, I believe the expected value of correct guesses given $n$ items is the $n$th partial of the harmonic series: $\displaystyle \sum_{k = 1}^n \frac{1}{k}$, which means the expected value approaches infinity as $n$ increases. – ferson2020 Mar 5 '13 at 14:43
• The question can't be answered in its current form because you haven't specified the payoffs for the game. If the payoffs favour quick solutions, there are non-trivial optimal strategies. For instance, for $n=3$, after incorrectly guessing, say, $1$ for the first slot, guessing, say, $2$ for the second slot offers a $1$ in $4$ chance of knowing after $2$ guesses that the arrangement is $321$ if the guess turns out to be right. By contrast, making another guess for the first slot is certain to lead to a total of three guesses. – joriki Mar 5 '13 at 17:16

There is no strategy that which takes less than $n(n-1)/2$ in the worst case. Consider a strategy (a menu of which questions to ask based on the history of previous answers). Consider a case in which all the questions asked result in negative answers (there may be many such cases if the strategy randomizes questions). Suppose the strategy concludes that the permutation is $P=(k_1,k_2,...,k_n)$. That is, the number $1$ is in slot $k_1$, number $2$ in slot $k_2$, ... and number $n$ in slot $k_n$. Consider another permutation $P'$ obtained from $P$ by swapping positions of numbers $i$ and $j$. The only way the strategy could have determined that permutation is $P$ and not $P'$ is by asking one of the following two questions: (1) Is number $i$ in slot $k_j$? or (2) Is number $j$ in slot $k_i$? Thus, for each pair $(i,j)$, the strategy should have asked at least one question. Since, there are $n(n-1)/2$ pairs, the strategy should have asked at least $n(n-1)/2$ questions.