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?

Solution 1:

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.