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

Solution 1:

For $n=2$ there is a better strategy. Flip two cards. If they match ($p=\frac 13$) you are done in two turns. If they don't match, flip one old and one new card. The improvement comes because these might match and if not, you know where all the cards are and are done in four turns. Now you have $\frac 13$ chance of being done in three turns, for an average of $3$. This carries over to longer games. Clearly the last turn in the discovery phase you should turn one of the unmatched old cards and one new card. You will match with probability $\frac 12$. If there are no unmatched old cards, turn the two new ones and they will match.

You can write a recurrence. Define $N(n,k)$ as the expected number of flips to deal with $n$ pairs when you know the locations of $k$ unmatched cards. From each flip you have the outcomes: they match, neither matches a known card, one matches a known card, both match known cards. I believe the best strategy is to flip two unkowns until there are only two, then flip one unknown and one known.

Solution 2:

A player with perfect memory will flip over cards in two distinct stages. First, he will flip over all the cards and find out what they are. Second, he will flip over all the matching cards. There is no difference in flipping over two cards that you know match as soon as you know they match and flipping over two cards that you know match after flipping all the cards over at least once. If he finds no matches in the first stage, then the total number of turns will be $2n$, because he flips over $n$ cards in the first stage and $n$ cards in the second stage. The only way for him to cut this time down is to find a match in the first stage. Ignore Everything Until the Second Edit The probability of this player picking a match on his first stage is the number of matches, $n$, divided by the number of ways to pick two matching cards out of $2n$ cards, which is $\frac{2n*(2n-1)}2=n*(2n-1)$. The probability of picking one match is therefore: $$\frac1{2n-1}$$ If you pick a match before you are finished with the first stage, then you can consider the same problem, but with $n-1$ instead of $n$ because that match is, in essence, removed. The probability of picking the second match is therefore: $$\frac1{2n-3}*\frac1{2n-1}$$ You can extend this reasoning to finding the third and greater number of matches. The expected number of matches found in the first string is therefore: $$1*\frac1{2n-1}+2*\frac1{2n-3}*\frac1{2n-1}+3*\frac1{2n-5}*\frac1{2n-3}*\frac1{2n-1}...$$ This means that you have to find the expected number of matches fewer than $n$ in the second stage, so the expected number of turns is: $$2n-(1*\frac1{2n-1}+2*\frac1{2n-3}*\frac1{2n-1}+3*\frac1{2n-5}*\frac1{2n-3}*\frac1{2n-1}...)$$ Finally, it is important to realize that if you find $n-1$ out of $n$ matches, you will have the last match left, so as soon as you reach the $(n-1)$th case, add one to the number of matches. For $n=2$, instead of having $2n-(1*\frac1{2n-1})$, you would have $2n-(2*\frac1{2n-1})$. For $n=3$, you would have $$2n-(1*\frac1{2n-1}+3*\frac1{2n-3}*\frac1{2n-1})$$

Edit: In my example where $n=3$, the $3*\frac1{2n-3}*\frac1{2n-1}$ part is accurate. However, the $1*\frac1{2n-1}$ part is not because I forgot to account for how many different ways there are to arrange the unmatched pairs. In this case, the number of possible combinations would be $4$, as Jens pointed out. I do not yet have a way to adjust for this.

Edit: Based on your results from your simulation, it seems that the expected number of turns has a formula of $$2n-\frac n{2n-1}$$ but I have no idea how to prove that.

Edit: This algorithm should work for the case in which a player can look at a card before flipping it over.

1. The player flips over two cards. If they match, he repeats this step. If not, he goes onto the next step.
2. The player then flips over the next unflipped card. If it matches one of the cards before, he flips over the matching card. If not, he flips over the next unflipped card. If this card matches a card flipped before this turn, then it does not matter if he matches them in the second stage, so, for clarity, he will. If this card does match the other card flipped in this turn, then it is a match and it is removed.
3. The player repeats the last step until he goes through all the cards. He then matches them up.

This algorithm should use up the fewest turns possible for this set up. The probability that the first card in one turn matches any of the previous cards is $\frac d m$, where $d$ is the number of distinct, unmatched cards already flipped over and $m$ is the number of remaining cards at the star of each turn. The probability that the second card matches the first card is $\frac 1 {m-1}$. The probability that the second card matched any of the previous cards but not the first card is $\frac {d-2} {m-1}$. The variable $d$ starts at $0$, increases by $1$ every time a card is flipped over and decreases by $2$ every time a match is found. The variable $m$ starts out as $2n$ and decreases by $1$ whenever a card is flipped over. From this, the question becomes "How many matches will we find on the first flip of a turn and how many matches will we find in a single turn?" Every match we find on the first flip or during a turn lowers the number of turns by $1$.