A game with 52 cards

Question

Alice and Bob play the following game with two (identical) standard decks of $52$ cards.

• First Alice secretly arranges one deck of $52$ cards in a long row on the table. All cards are face-down, and Bob has no knowledge of the positions of any of the cards.
• Then the game goes through several rounds. In every round, Bob first pays $1$ Euro to Alice. Then Bob arranges the second deck of cards in a long row on the table, parallel to Alice's row and with all the cards face-up. Then Alice tells Bob all the face-up cards in his row that agree with the corresponding face-down cards in her row. Then the next round starts.
• The game ends, as soon as Bob knows the positions of all the face-down cards in Alice's row. Bob then receives $x$ Euros from Alice.

Question: What is the smallest value of $x$, for which Bob can still avoid (with absolute certainty) to lose any money?

Answer 1

An upper bound

51 Euro.

Bob picks a random permutation of the deck and then rotates the subset of his deck that does not match Alice's. The worst case is when the whole deck is a rotation of his initial permutation, in which case he has to rotate 51 times.

Answer 2

I think the worst case scenario is 52 tries. That scenario is where each guess (until the last) is completely wrong. Your first guess is shifted by 1, and subsequent guesses are just shifting the cards, but in the wrong direction. On the 52nd guess, all the cards will line up. Since you can disregard the last guess (you know the guess), Bob has to pay 51 Euro.

That's an unlikely scenario, since you're likely to make some right guesses during that time; you just skip over those cards when shifting.

Answer 3

A lower bound is

$51$.

Represent the game as a bipartite graph $G$ on the set of cards 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 card $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 card 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 cards 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 cards $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)$.

When Bob finally knows the correct order, only one perfect matching of $G$ remains. By the claim, there is some elusive card $a$ which has degree $1$ but has only ever had adjacent edges removed through guesses by Bob, requiring at least $51$ guesses.

Answer 4

If we can agree that not knowing a card is always less informative than knowing a card, then I guess we can show the lower bound too. I'm not exactly sure how obvious this assumption is.

Carl's suggested strategy maximizes information in the sense that in each turn there is no dead guess for any card. Even when guesses are wrong, on each turn and for each card at least one possibility is excluded. The only way to do better is by guessing some other card right (thus excluding more possibilities). Therefore, in the worst case scenario, on each turn and for each card we exclude exactly one possibility, so that after $51$ turns we are done.

Another way to think of this is as follows. Rather than consider the worst case scenario for finding out the entire sequence of cards, consider the worst case scenario for finding out a single given card, say the first. On each turn, we can exclude at least one possibility for the first card, so the worst case scenario cannot be worse than $51$ turns. On the other hand, the only way we can do better is if, before then, we guess some other card right and that guess had not yet been made for the first card.

In the worst case scenario, these correct guesses don't happen (here is where I've used the assumption). In other words, the worst case for guessing correctly the first card is $51$ turns. Surely, the worst case for guessing correctly the entire sequence can't be better, so it too must be $51$ turns.

Answer 5

The optimal worst case it requires

51 tries

To show that, Try the game with 2 cards, let's call them A and B. In the worst case;

A B (all face down)

B A

would be the first try. So Alice would not tell anything since no match up is available. In the game rule it is stated that;

The game ends, as soon as Bob knows the positions of all the face-down cards in Alice's row. Bob then receives xx Euros from Alice.

So before the next game begins, Bob knows the positions and he gets the money, which should be 1€ at least! So with two cards, 1 try is enough to find at worst optimal case.

For 3 cards;

A B C

B C A

Then no response from Alice; Next try will be (unluckily)

A B C

C A B

Then Bob knows all face down cards automatically, so 2 tries would be enough. Then 2€ for 3 cards.

For 4 cards; it makes 3 tries and 3€ not to lose any money at least!

As a result;

For 52 cards it has to require 51 tries and 51 Euros at the worst optimal case! At worst case, Bob will strangely never find any card until the last try, which is kinda very low chance!

Answer 6

The smallest value of x, for which Bob can still avoid (with absolute certainty) to lose any money is:

€51

He starts off knowing Alice's order is one of 52! orders. Let us imagine Bob can keep a list of this vast amount of orders. When he pays €1 he receives some information: "these positions are correct and the rest are not". He now deletes impossible orders and will have a smaller number of possible orders left - those forming the intersection of those orders that match at positions he has matched so far and those that do not match any of his attempts so far at positions he has not yet matched.

If, in any round, Bob:

1. places a matched card in an as yet unmatched position;
2. places an unmatched card in a matched position; or
3. places an unmatched card in a position he has already tried for said card

...then he will receive some information he already knew (he knew that card did not go there) and hence will, in expectation, reduce his list of possible orders by less than if he avoided doing so.

Furthermore, since he will know Alice's order if he matches all but two positions, he should

4. avoid possible orders that include any pairwise transpositions of two positions of previously unmatched cards

...as there is a chance he will get this information for free. Note, however, that this does not affect the worst case performance, but does affect the expected performance (see this follow up question).

One way, and by far the easiest, to assure he avoids all four of these scenarios is the cycling unmatched cards method given by Carl Löndahl.

Since Bob is avoiding at least 1. 2. & 3 to maximise his information and the information gained from making a match is at least as much as the information gained from making a non-match, the worst case is necessarily not matching any cards all the way to round N-2 and then matching some number (possibly zero) of the cards in round N-1 which then reduces his possible orders to 1.

If we label Bob's order as
(0,1,2,3,...,N-2,N-1)
then for a cycling of unmatched cards there are two worst case orders for Alice to have chosen, if we cycle rightwards then
(1,2,3,...,N-2,N-1,0) has no matches in round N-1, and
(2,3,...,N-2,N-1,0,1) matches all in round N-1;
if instead we cycle leftwards they would be
(N-1,0,1,2,..,N-2) and
(N-2,N-1,0,1,2,...) respectively.

---

As an example of the fourth point one can compare Carl's method with choosing the first of the possible orders when they are listed in lexicographical order for all cases of a four card game. If we label Bob's starting choice as (0,1,2,3) and have him cycle leftwards, then his costs for each of the 24 orders Alice could choose are:

When using the first lexicographically listed order, when Bob does not match any in the first round using (0,1,2,3) then his next round choice will be (1,0,3,2), which, while being a possible order, happens to be two pairwise transpositions of his first round attempt. This helps him in one of the two worst cases he would experience from cycling unmatched cards (if he was cycling rightwards it would help him with the other instead), but hinders him in three cases. The worst case scenario is the same, but the expected cost rises from $\frac{43}{24}$ to $\frac{45}{24}$.