mathematics - Corollary to "A game with 52 cards"

Inspired by A game with 52 cards

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.

The original problem asked for the minimum risk-free wager. Instead:

What is the minimum payout $x$ for Bob to break even on average?

Answer

Bob randomly place his card deck. Alice indicates the cards that are correct. All the other cards have exactly one non-match that should never be tried again.

Bob rotate all the cards that were incorrectly placed, one spot to the right (the right most card going back at the left). Alice indicates the cards that are correct. All the other cards have exactly two non-match that should never be tried again.

Bob rotate to the right all the cards that were incorrectly placed. etc...

In less than 52 test Bob get his answer.

Running this on 10 000 cases I got the following statistics (in bold is the cost):

• 17: 1 time



• 18: 2 times


• 19: 15 times


• 20: 66 times


• 21: 187 times


• 22: 470 times


• 23: 934 times


• 24: 1471 times


• 25: 1864 times


• 26: 1864 times


• 27: 1476 times



• 28: 906 times


• 29: 463 times


• 30: 207 times


• 31: 53 times


• 32: 19 times


• 33: 2 times

Which gives an average of 25.4949. I would play this game if $x\geq26$.

Here is a typical run (in white Alice deck):

Let's solve the problem of correctly placing $l$ cards of a $k$-card deck on the first try for a $k$-card deck. Luckily this is exactly what is counted by the rencontres numbers $D^k_l$. (rencontre is French for encounter.) And of which a closed expression is given by:

$$D^k_l = \begin{cases}\binom k l \times \left[ (k-l)! \over e \right] & \text{when $k > l$} \\ k! & \text{when $k = l$}\end{cases}$$ where $[x]$ stands for x rounded to the nearest integer.