How many turns, on average, does it take for a perfect player to win Concentration (adjusted)?

Question

Let's say a person with perfect memory is playing the card-matching game Concentration. He/she randomly lays out 2n cards (ie. n card pairs) sorted randomly and repeatedly takes turns consisting of flipping over two cards, one at a time (so you may look at the first card before flipping a second). When the cards match they are removed from play. When cards do not match, they are turned back over. The player wins when all pairs are found and all cards are removed.

A perfect game is played in just n turns, but even a perfect player (one with perfect memory) couldn't hope to come close to a perfect game as there would still be a lot of guessing required.

How to you calculate the expected number of turns required to win for player with perfect memory?

NOTE: this is a modification of this very similar question

Answer 1

I claim that the proper strategy is

1. If you know of a pair, flip it
2. Otherwise, for the first flip of a pair, turn an unknown card
3. For the second flip of a pair, if you can match the first do so
4. Else turn an unknown card

Item 1 can occur any time you want, so it might as well be first. Otherwise, turning a known card gives no information, so you should turn an unknown. Item 3 is clear-if you turn another card you are one flip behind. Again for 4, you get information that you don't if you flip a known card.

Now we can define a function $N(n,k,m)$ which is the expected number of flips with $n$ pairs on the board, $k$ cards known and $m=1$ indicates that we have a match among the known cards. It only is defined before we flip the first card of a pair. When we turn the first card of a pair, we have two possible results-it matches a known card or not. Assuming it does not, when we turn the second card, it can match the first card turned, it can match another known card, or it can be new. The recurrence is $$N(n,k,1)=1+N(n-1,k-2,0)\\N(n,k,0)=1+\frac k{2n-k}N(n-1,k-1,0)+\frac {2n-2k}{2n-k}\left(\frac{k+1}{2n-k-1}N(n,k+2,1)+\frac {2n-2k-2}{2n-k-1}N(n,k+2,0)\right) $$ where the first comes from flipping the known pair. The $1$ in the second is this flip. The first term after the $1$ is from flipping a card that matches a known one, so you flip the match. The first term in the last parenthesis is from flipping an unmatch, then flipping a match. The second is from flipping two unmatches.

Answer 2

It is possible that this solution is just a reformulation of @RossMillikan.

Some notation: We denote by $C(n,k)$ a slightly modified game of concentration with $2n+k$ cards and $n$ couples.

Consider a game of $n$-concentration (i.e. $n$ couples). The strategy we use is the following:

1. The first move is to flip two cards. If they match, we are in the situation of a game of $(n-1)$-concentration and we repeat this process until either we have finished the game, or we find two cards that don't match. In this case, not considering the two cards just flipped, we are in the situation of $C(n-2,2)$.
2. We are in the situation $C(n,k)$, where the $k$ singletons are known cards (those of which we have already flipped the companion). Flip an as of yet never flipped card. If it is one of the $k$ singletons, pair it with its partner and we get to $C(n,k-1)$, else flip a second card and we have three possibilities. Either we find a couple with the first card we flipped, so that we find ourselves in $C(n-1,k)$, or the second card matches with one of the $k$ singletons, so that the next move is to eliminate the found couple and we are in $C(n-1,k)$, or we find two new singletons, landing in $C(n-2,k+2)$.
3. Go on like this until the game is done.

Now for the expected number of turns. Abusing of notation, I write $C(n,k)$ for the expected value of a game $C(n,k)$. We have the obvious formulae \begin{align} C(0,k) = & k,\\ C(1,0) = & 1,\\ C(n,0) = & 1 + \frac{1}{2n-1}C(n-1,0) + \left(1-\frac{1}{2n-1}\right)C(n-2,2),\\ C(n,k) = & 1 + \left(1-\frac{k}{2n+k}\right)\left(\frac{1}{2n+k-1}C(n-1,k) + \frac{k}{2n+k-1}(1+C(n-1,k)) + \frac{2n-2}{2n+k-1}C(n-2,k+2)\right) + \frac{k}{2n+k}C(n,k-1). \end{align} This allows to dynamically compute the expected number of moves. I believe this strategy to be optimal, but I have no idea how to prove it. I don't know if there is a closed formula for $C(n,0)$.

---

Computationally, for low values of $n$ I got: \begin{align} C(1,0) = & 1\\ C(2,0) = & \tfrac{8}{3},\\ C(3,0) = & \tfrac{13}{3},\\ C(4,0) = & \tfrac{622}{105},\\ C(5,0) = & \tfrac{793}{105}. \end{align} If anyone wants more data in order to conjecture a closed expression for $C(n,0)$ I will be happy to provide it.