Update: Bram28 and Barry Cipra have given very good answers! I've also fixed a lot of my examples because of the better solutions. Also, as per Barry Cipra suggestion, I've created a follow-up question here, for more disscusion.
A few days ago my friend and I were participating in a card game and after playing it he was interested in the game theory perspective of the game. At first, we thought it would be pretty fun to think about, but quickly we realized that it was going to be way harder than we initially considered it was.
So, we reduced the conditions on the game to try to solve simpler cases, and it turned into this:
The Game:
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 (I will give an example below).
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.
The 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.
The question is: Will this game always end in a finite amount of turns?
Examples:
Let's call the players A and B, with A always having the first move. Then,
n = 2:
This is trivial. If A sees that B has 2, then A knows that he must have 1 and says "higher", and then he ends the game. The same goes if B has 1.
n = 8:
Let's say that A has 2 and B has 3.
-
Turn 1: A sees that B has 3, and says "higher" since he has a bigger chance of getting a card between 3 and 8 compared to 1 or 2.
-
Turn 2: B hears "higher", so he deduces that he must be between 1 and 4. But he sees that A is 2, and he also knows that he cannot be 1, or A would have ended the game on the 1st turn, so he also says "higher" and ends the game.
n = 5:
(Bram28 gave a solution.) Let's say that A has 2 and B has 3.
-
Turn 1a: A sees 3, so he randomly guesses higher.
-
Turn 2a: B hears "higher", but doesn't know if A is just guessing (in which case he must be a 3) or if A is being real (in which case he can be 2). But at least he can conclude that he is either 2 or 3. Now B sees that A is 2, and so he must be 3. B then ends the game with "higher".
-
Very similarly, B can also end the game if A says lower.
Thanks for reading!
Best Answer
In answer to the official question, Will the game always end in a finite number of turns?, the answer is Yes, by induction:
As noted, if $n=2$, each player knows their own card as soon as they see their opponent's, so the game ends on the opening move. In general, if either player sees their opponent holding the card labeled $n$, they immediately know their own card, whatever it is, is lower, and so they can end the game on their first turn. Thus if the game goes beyond the first round, then both players know that neither of them has the card labeled $n$, at which point they both know they are, in effect, playing the game with only $n-1$ cards.
In fact, if the game goes beyond the first round, both players know that only $n-2$ cards are "in play," namely the cards labeled $2$ to $n-1$. If it survives the second round, they both know only cards labeled $3$ to $n-2$ are possible, and so forth. So the game won't last more than $\lceil n/2\rceil$ rounds before one of the players is certain whether their own card is higher or lower than their opponent's.
Note, none of this depends on what either player guesses when they're not sure. Those guesses can only quicken the pace of the game. For example, departing somewhat from the OP's third precondition on play, each player could signal, in binary, the value of their opponent's card with a sequence of guesses "I think your card is higher (1) than mine" or "I think your card is lower (0) than mine," which, if $n=2^m$, will end the game in at most $m$ rounds (at which point the second player will know the exact value of both cards).