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

Represent the game as a bipartite graph $G$ on the set of numbers and the set of positions. The game starts with a complete bipartite graph. Every turn, Bob guesses a perfect matching (of the complete bipartite graph). For each guessed edge $ab$, if Alice says it is wrong, then $ab$ is removed; otherwise, all other edges adjacent to $a$ and $b$ are removed. If at any point an edge is impossible, i.e., not in any perfect matching, then it is removed. The game ends when only one perfect matching remains.

Alice's adversarial strategy will be to say that a number $a$ is in the correct position $b$ only if she has to, i.e., $a$ and $b$ are adjacent only to each other in $G$. Then an edge is only ever removed when either Bob guesses it or it is impossible. Call a number elusive if it has only ever had adjacent edges removed through guesses by Bob, not because they were impossible. Call a connected component of $G$ elusive if all of its numbers are elusive.

Claim: $G$ always has an elusive connected component.

Proof: $G$ starts as one elusive connected component. Suppose at some point in the game, the impossible edge $xy$ is removed from the elusive connected component $C$ with set of numbers $X\ni x$. Then there is $U\subseteq X\setminus\{x\}$ that violates Hall's condition in $C-x-y$ but not in $C$, so $|U|=|N(U)|$. Then $U$ must be matched with $N(U)$, so every edge between $X\setminus U$ and $N(U)$ can be removed to leave an elusive connected component induced by $U\cup N(U)$.

Just before Bob finally guesses correctly, only one perfect matching of $G$ remains. By the claim, there is some elusive number $a$ which has degree $1$ but has only ever had adjacent edges removed through guesses by Bob, requiring at least $n-1$ guesses. Then Bob needs at least $n$ guesses.

Answer 2

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 3

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.