What is the minimum amount of moves it takes to finish this game?

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.

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.

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.

Update:

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.

In addition to my lengthy analysis earlier, I got a few more results:

For $$n=13$$ and $$n=14$$ it is still only 3 moves! If after two moves the game has not already ended, then if we got to $$HH$$, we know that $$A$$ is looking at a number (i.e. $$B$$ has the number) from $$2-7$$, while $$B$$ must be looking at a number (i.e. $$A$$ has the number) $$3$$ or $$4$$. So, if $$A$$ sees $$2$$ or $$3$$, $$A$$ knows that his/her own number is higher than $$B$$'s, and when $$A$$ sees anywhere from $$4-7$$, $$A$$ knows his/her number is lower than $$B$$ 's, and so in every case $$A$$ can end the game. The same goes for $$HL$$, $$LH$$, and $$LL$$.

For $$n=15$$ we finally need $$4$$ moves: If after two moves we get to $$HL$$, then that means $$A$$ is looking at $$2-8$$, and $$B$$ is looking at $$5-7$$. So, if $$A$$ sees anything but $$6$$, $$A$$ can end the game, but if $$A$$ sees $$6$$, then $$A$$ has to say something ... after which $$B$$ knows that $$A$$ is looking at a $$6$$ and can finish the game on turn $$4$$

OK, so it looks like it's going to be a log function: With $$n=2$$ it takes $$1$$ move, but for $$n=3$$ it takes a maximum of $$2$$ moves: if $$A$$ sees a $$2$$, $$A$$ has to say something, and $$B$$ will end the game on the next move, knowing that $$A$$ is looking at a $$2$$ (otherwise, $$A$$ would have ended the game immediately). With $$n=4,5,6$$ the game still takes a maximum of $$2$$ moves, but we went up to $$3$$ moves for $$n=7$$. And now we see that for $$n=14$$ we have still have a maximum of $$3$$ moves, but then for $$n=15$$ we move up to $$4$$. In other words, the hypothesis is that it will take a maximum of

$$\lfloor log_2 (n+1) \rfloor$$

moves to end the game.

OK, on to the proof ....

We do this by induction of course. Let's prove that for any $$n$$, where $$2^m-1 \le n \le 2^{m+1}-2$$, the game with $$n$$ cards takes a maximum of $$m$$ moves.

Base: already verified up to $$n=15$$

Step:

Let's say that we have $$n$$ cards. It is clear that in order to get to the maximum number of games, $$A$$ and $$B$$ need to have both of their cards in the lower half (which includes the middle card if $$n$$ is odd), or both in the upper half (which again includes the middle card if $$n$$ is odd), or else the game ends very quickly. So, by symmetry, we can just assume that they are both in the lower half and that $$A$$ says "higher". This means that $$B$$ does not have card $$1$$, or $$A$$ would have ended the game right away. Thus, in effect, we are now in a situation where we have cards $$2$$ through $$\lfloor (n+1)/2 \rfloor$$ still in play.

The lower bound is $$2$$ because the game did not ended yet after $$A$$'s turn. Of course, if $$B$$ sees a $$1$$, $$B$$ would end the game right there as well, but that is simply the counterpart of $$A$$ being able to end the game when seeing the lowest (or highest) card.

The upper bound is $$\lfloor (n+1)/2 \rfloor$$, because if $$n$$ is even, then the upperbound of the lower half of the cards is exactly $$n/2$$, which equals $$\lfloor (n+1)/2 \rfloor$$, and if $$n$$ is odd, then the upper bound should include the middle card, which is $$(n+1)/2$$. And again, while $$B$$ could end the game immediately when seeing the middle card after $$A$$'s turn, we should not throw this one out. Rather: $$B$$ seeing the middle card would be the counterpart of $$A$$ seeing $$n$$ on turn $$1$$, and just as $$A$$ could end the game upon seeing $$n$$, $$B$$ can end the game upon seeing $$(n+1)/2$$.

OK, so if the game does not end at $$A$$'s turn, and we are in a 'maximum turn' game, then we effectively have ended up with a game with cards $$2$$ through $$\lfloor (n+1)/2 \rfloor$$ or, what is the same thing, a game with cards $$1$$ through $$\lfloor (n-1)/2 \rfloor$$.

Now, with a little basic math you can verify that if $$2^m-1 \le n \le 2^{m+1}-2$$, then $$2^{m-1}-1 \le \lfloor (n-1)/2 \rfloor \le 2^{m}-2$$:

For the lower bound $$n=2^m-1$$, we get that :

$$\lfloor (n-1)/2 \rfloor = \lfloor (2^m-1-1)/2 \rfloor = \lfloor (2^m-2)/2 \rfloor = 2^{m-1}-1$$

while for the upper bound $$n=2^{m+1}-2$$ we have:

$$\lfloor (n-1)/2 \rfloor = \lfloor (2^{m+1}-2-1)/2 \rfloor = \lfloor 2^m-1-1/2 \rfloor = 2^m-2$$

and so by the inductive hypothesis it will take a maximum of $$m-1$$ moves to end this game which, combined with $$A$$'s initial turn, means that the game with $$2^m-1 \le n < 2^{m+1}-1$$ cards will indeed take a maximum of $$m$$ moves to end.

• Hey, I've added some new bounds for the solution. It looks like the maximum will be some kind of $log_2$ function. But otherwise, I've hit a wall. – Hanting Zhang Oct 28 '18 at 22:12
• @HantingZhang OK, I got the proof – Bram28 Oct 30 '18 at 19:02