This is a follow up question from this post which I asked. The previous question was answered by Barry Cipra, and I was suggested to create this follow up question.
Two players have $n$ cards labeled from $1$ to $n$. They each take a card from the deck at random and then hold it up at their foreheads. The players cannot see their own card but they can see the other players card.
Now the players take turns making guesses on whether they are "higher" or "lower" than the other player.
The goal is for both players to work together to figure out each of their respective positions. The game ends when one (not both) of the players decides that they are sure of their position. The player will not end the game unless they are 100% sure that he is right.
Other preconditions are:
- Both players know $n$.
- Both players are perfect logicians with infinite memory and both also know that the other player is a perfect logician.
- The players know that they will always make the more likely guess, and will choose randomly if both choices have equal chances of happening. But there cannot be some other predetermined strategy.
In brief, I want to find a function, $M(a, b, n)$, which returns the minimum amount of moves it would take for player A with card $a$ and player B with card $b$ to finish the game, given $n$, the maximum card in the deck.
From Bram28's detailed answer, it is already known that for $n < 11$, the games will never go past 3 moves.
Ok, I've thought about it a bit more. Actually, it turns out that most games end very quickly. By symmetry, we can always choose A to go first and for B to a card that is $b \leq n/2$, for even $n$.
- Turn 1: A will say "higher".
- Turn 2, Case 1: Now B knows that he must be less than $n/2$. If A's card is greater than $n/2$, then B says "lower" and the game ends in 2 turns.
- Turn 2, Case 2: Otherwise, if A is less than or equal to $n/2$, B will have to say "higher" or "lower", accordingly, but can't conclude his position.
- Turn 3: If the game reaches turn 3, then A knows that he is in Case 2, and can conclude something from B's answer in turn 2. Now A and B both know that they're less than $n/2$, but can't be certain of their relative position, so, we've gone right back to the beginning of the game, except with $n/2$ cards.
The condition for the game to end at Turn 2 is for B to be less than $n/2$ and A to be greater than $n/2$ (or the other way around), which is about a half of the possible choice of cards for A and B.
We can also apply this recursively, to find a bound on decks with $ n = 2^m$, for which the maximum amount of moves that can be played is $2\log_2 n = 2m$. For even numbers in general, the 2 players can "weed out" the factors of 2 until they're left with an odd number, which is tricky since we have the middle term, where A can't make any inference about his position on the first turn.
Thanks for reading!