Prove that this card game between 2 people always ends in a finite amount of moves.

Question

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!

Answer 1

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).

Answer 2

The $n=5$ case with $A$ having a $2$, and $B$ having a $3$ will actually end very quickly:

$A$ sees a $3$, and randomly says "higher"

From this, $B$ can infer that $A$ is looking at a $2$ or $3$, for if $A$ would see a $1$, $A$ would have ended the game right then and there. So, seeing $A$'s $2$, $B$ know that $A$ uis in fact no looking at a $2$ either, and so $A$ must be looking at a $3$, and so now $B$ knows the ordering. So this game ends on move $2$

Notice that the $n=6$ case similarly ends in two moves at most: If $A$ looks at $1$ or $6$, $A$ will end the game on the first move. If not, then if $A$ says ":higher", then $B$ knows $A$ is looking at $2$ or $3$. So, if $B$ sees $1$, $B$ will end game, knowing his/her card is higher, and if $B$ sees $4$, $5$, or $6$, $B$ can end game as well, knowing that his/her card is lower. So that leaves $B$ seeing $2$, in which case $B$ knows $A$ is looking at $3$, or vice versa, and so in both of those cases $B$ can end game as well. And, by symmetry, the same holds for $A$ looking at a $4$ or $5$.

Case $n=7$ has a max of $3$ moves:

Here is a table that shows the first (and only) or first two moves:

E = Ends game

H = says "higher"

L = says "lower"

? = randomly says "higher" or "lower"

X=impossible (same card)

Top row: the card that $A$ has

Left column: the card that $B$ has:

\begin{array}{c|c|c|c|c|c|c|c|c|} &1&2&3&4&5&6&7\\ \hline 1&X&E&E&E&E&E&E\\\hline 2&HE&X&HH&HE&HE&HE&HE\\\hline 3&HE&HE&X&HE&HE&HE&HE\\\hline 4&?E&?E&LE \ or \ HH & X&HE \ or \ LL&?E&?E\\\hline 5&LE&LE&LE&LE&X&LE&LE\\\hline 6&LE&LE&LE&LE&LL&X&LE\\\hline 7&E&E&E&E&E&E&X\\\hline \end{array}

Just to explain this a little further: take the entry where $A$ has $2$ (column $2$) and $B$ has $5$ row $5$). Seeing as $B$ has $5$, $A$ will say "lower". So, $B$ knows $A$ is looking at $4$,$5$,or $6$ (not $7$, or otherwise $A$ would have ended game immediately, as you see in row $7$ ... likewise row $1$ immediately ends the game). So, seeing a $2$, $B$ knows $A$'s number is definitely lower, and so can end game in move 2: $LE$

Here is a tricky entry: $A$ has a $3$, and $B$ has a $2$. $A$ says "higher". Now $B$ thinks: OK, so $A$ is looking at a $2$, $3$, or $4$. Now, I see a $3$, so actually $A$ is either looking at a $2$ (and so definitely says "higher", or $A$ is looking at $4$, and randomly said higher. So, the conditional probability that $A$ has a $2$ given that $A$ said "higher" is greater than the conditional probability of $A$ having a $4$ given that $A$ said "higher". That is, it is more likely that $A$ has a $2$ than a $4$, and so I should definitely say "higher" as well. So, this entry becomes $HH$. By the same reasoning, $A$ having $5$ and $6$ having $6$ becomes $LL$.

You can verify the others yourself ... but as you can see, there are only $4$ situations where the game has not yet ended after two moves: We got to $HH$ when $A$ has $3$ and $B$ has either $2$ or $4$. But then when it is $A$'s turn again, then seeing as $B$ has not ended the game, and given as we got to $HH$, $A$ knows that $B$ must have been looking at a $3$, and so $A$ can now end the game. Same for the other two situations that led to $LL$, as now $A$ knows that $B$ is looking at a $5$.

OK, just did $n=9$: this one also ends in $3$ moves! After moves 1 and possibly 2:

\begin{array}{c|c|c|c|c|c|c|c|c|} &1&2&3&4&5&6&7&8&9\\ \hline 1&X&E&E&E&E&E&E&E&E\\\hline 2&HE&X&HH&HE&HE&HE&HE&HE&HE\\\hline 3&HE&HE&X&HL&HE&HE&HE&HE&HE\\\hline 4&HE&HE&HH&X&HE&HE&HE&HE&HE\\\hline 5&?E&?E&LE \ or \ HH &LE \ or \ HL & X&HE \ or \ LH&HE \ or \ LL&?E&?E\\\hline 6&LE&LE&LE&LE&LE&X&LL&LE&LE\\\hline 7&LE&LE&LE&LE&LE&LH&X&LE&LE\\\hline 8&LE&LE&LE&LE&LE&LH&LL&X&LE\\\hline 9&E&E&E&E&E&E&E&E&X\\\hline \end{array}

OK, so there are a number of ways in which this game has not ended yet after 2 moves, but if it hasn't ended yet, and we got to $HH$, $A$ knows that must have been because $A$ has a $3$, and can end game accordingly. Similarly, the only way we could have gotten to $HL$ is when $A$ has a $4$; $LH$ means $A$ has a $6$, and $LL$ means $A$ has a $7$. Being a perfect logician, $A$ can make this inference in each of these cases, figure out his/her own card, and a quick look at $B$'s card then tells $A$ the correct order. So yes, also for $n=9$ this game ends in $3$ moves

$n=10$ works out very similarly: after two moves $A$ knows his/her card: $HH$ means $A$ has $3$, $HL$ means $A$ has $4$, $LH$ means $A$ has $7$, and $LL$ means $A$ has $8$. So also this game ends in $3$ moves.

$n=11$ is interesting: Both $A$ having $4$ and $A$ having $5$ could lead to $HL$. But this is only when $B$ has $3$, $4$, $5$, or $6$ and so in all cases $A$ can end game. So: still only $3$ moves.