Guess the right permutation game

Question

Consider the following game (somewhat similar to Bulls and Cows): player A selects a permutation of $n$ different numbers, say $1$ to $n$. Player B then has to guess the permutation: he suggests some permutation and A has to reveal which numbers are exactly at their right place (but nothing else). Player B then guesses again, and so forth, until he gets the right permutation.

Question: supposing B's best strategy, what is the worst-case number of guesses (including the last right guess) he would have to make?

Note: it is easy to see that the upper bound on the worst case is $n$. The direct analysis for $n=3$ and $4$ seems to suggest that it is exactly $n$, but I can't quite prove the lower bound.

Answer 1

You can probably argue something like the following: $A$ can choose the permutation while answering the questions of $B$ in such a way that it is consistent with the answers given so far and makes it as hard as possible for $B$ to get it right soon. Then, when $B$ asks the first question, $A$ just chooses a permutation where no digit is in the right spot. Then $B$ asks another permutation and $A$ chooses a permutation for which no digit is in the right place in the first nor second of $B$'s guesses. This can go on $n-1$ times (you should be able to prove this, I hope, since I have not done it myself). In the $n$'th turn, $A$ can not avoid losing.

Answer 2

Edit 4/1/19: User noedne in comments has pointed out a flaw in my answer (from nearly five years ago). I don't have an easy fix for it, so I'm just pointing out, for now, that this answer is wrong and the OP would do well to unaccept it.

I'm leaving the original answer as is, for what it's worth:

Let's assume, sensibly enough, that $B$ never tries the same "wrong" position for any number twice. Let's also assume that once she learns the correct position for a number, she keeps it there in all subsequent rounds. In that case, $A$ can make the game take $n$ rounds by saying "nothing is in correct position" on the first round," "$1$ is correctly placed" in round $2$, "$1$ and $2$ are correctly placed" in round $3$, and so forth, with "everything up to $k$ is correctly placed" in round $k+1$ until round $n$ when the final answer is "everything is correctly placed."

Should $B$ ever depart from playing sensibly in such a way that on some round $k+1$ the number $k$ is in a position it's been in before (hence already known to be "wrong") but some other, larger number, $K$, is in a new position, $A$ can simply mentally swap $k$ and $K$ and proceed as before. Should $B$ ever play stupidly, and put all the yet-to-be-located numbers in positions that have already been ruled out, $A$ can basically just say so.