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

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, without looking at the first card. 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?

---

EDIT 2 -- clarifying the rules

Since all the early answers seem to read this question as you CANNOT look at the first card, I'm editing that into the rules.

I originally was thinking you CAN look at the first card (since that's how I'd learned the game and, to my knowledge, that is how it is usually played.

For that rule adjustment, I've posted a new question here: How many turns, on average, does it take for a perfect player to win Concentration (adjusted)?

---

EDIT -- Checking answers against a simulation

The strategy proposed in AlgorithmsX's answer seems to make sense to me - that is, the game takes place in two distinct stages.

Stage 1: flip all cards to learn where they are, and...

Stage 2: clean up/perfectly find all matches (since you know where they are).

Thus improving on a $2n$ turn game is pure chance; how many matches do you find in Stage 1?

To check a given answer, I wrote the below code to simulate the problem. It just randomly shuffles an array with pairs from $0$ to $n-1$ and checks for adjacent pairs that would come up in the sweep during Stage 1 (so a 0-1 pair is a match, but 1-2 is not). This seems like a good way to check answers because (for me personally, at least) it's easier to reason about the simulation than the math.

Currently, AlgorithmsX's answer for $n=3$ results in $5.6$, but I would expect it to be $5.4$ barring any errors in my simulation.

Some simulated results (1 million trials)

n | 2 | 3 | 4 | 5 | 6 |

turns | 3.33 | 5.40 | 7.43 | 9.44 | 11.45 |

Code to simulate answer given $n$

function shuffle(array) {
  var currentIndex = array.length, temporaryValue, randomIndex;

  // While there remain elements to shuffle...
  while (0 !== currentIndex) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    // And swap it with the current element.
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }

  return array;
}

var simulation = function(n, nTrials){

  // make array from 0 to n-1 with pairs
  var cards = Array.apply(null, {length: n}).map(Number.call, Number);
  cards = cards.concat(cards);

  var totalTurns = 0; 
  var trialsLeft = nTrials;

  while(trialsLeft>0){
    cards = shuffle(cards)
    var matches = 0;
    for(var i=0; i<n; i++){
      if(cards[2*i]===cards[2*i+1]){
        matches++
      }
    }
    totalTurns += 2*n-matches;
    trialsLeft--
  }
  return totalTurns/nTrials;
}

Answer 1

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$.

Answer 2

I think I have an answer, though it's not very beautiful.

Let's first look at a small example with $n=2$. Let the $2$ pairs of cards be represented as $\{A,A\}$ and $\{B,B\}$. We then have the following possible arrangements of the cards in a row:

1. $AABB$
2. $ABAB$
3. $ABBA$
4. $BAAB$
5. $BABA$
6. $BBAA$

The total number of arrangements is $6$. In general, the total number of arrangements of n pairs of cards will be $$TA(n) = \frac{2n!}{2^n}$$

We now flip the cards, $2$ at a time, starting from the beginning of a row. If the $2$ cards are not a pair, we turn them back over again. For arrangements $1$ and $6$ we only need to do $2$ flips and we are done. For arrangements $2-5$ we need to do $2$ flips to reveal the cards and then $2$ flips to do it pairwise, in all $4$ flips. The expected number of turns for $n = 2$ is thus $$\begin{align} E(2) & = \frac{2*2+4*4}{6} \\\\ & = 3\frac{1}{3} \end{align}$$

I'm going to make a second (and last) example, but before I do, I'm going to make some definitions. An arrangement of $n$ pairs has $k$ pairs aligned if $k$ pairs are revealed in the first flip-through of the arrangement. The number of arrangements in which $k$ pairs are aligned will be expressed as $A(n,k)$. Thus, $A(2,2)=2$ as we saw in the first example. Similarly, $A(2,1)=0$ (it is not possible to have $n-1$ pairs aligned) and $A(2,0)=4$. In the following example I'm going to work out the formula for $A(n,k)$. If there is an easier way, please let me know!

Now let's look at the example for $n=4$. For obvious reasons I'm not going to list all possible arrangements but will only look at the arrangements where there is at least $1$ aligned pair, i.e. $k\ge 1$:

$\underline{k=4}$

We have 4 aligned pairs, e.g. $AABBCCDD$. These can be permutated in $4!$ ways. This must be true in general, i.e. with $n$ pairs of which $n$ are aligned we have $$A(n,n)=n!$$

$\underline{k=3}$

There can be no arrangement where there are exactly $3$ aligned pairs. If there are $3$ aligned pairs, the last two cards must also be aligned. In general $$A(n,n-1)=0$$

$\underline{k=2}$

Let me the list the possible scenarios using the pairs $\{A,A\}$ and $\{B,B\}$ as an example (the "x" represents cards not aligned in pairs):

1. $AABBxxxx$
2. $AAxxBBxx$
3. $AAxxxxBB$
4. $xxAABBxx$
5. $xxAAxxBB$
6. $xxxxAABB$

There are $\binom{4}{2}=6$ scenarios with these $2$ pairs. However, all possible combinations of pairs must be considered and there are $4*3$ such combinations. In addition, for each scenario we must consider in how many ways the non-aligned cards can be permutated. Luckily, we already know this from the example with $n=2$. The number of ways $2$ pairs can be arranged with $0$ aligned pairs is $A(2,0)=4$. We therefore find that $$A(4,2)=\binom{4}{2}*4*3*A(2,0)$$ The generalized version of this formula is the following: $$A(n,k)=\binom{n}{k}*\frac{n!}{n-k}*A(n-k,0)$$

There are some issues with the term $A(n-k,0)$, but I will get to that later.

$\underline{k=1}$

This is similar to the case with $k=2$. With $1$ aligned pair the scenarios are:

1. $AAxxxxxx$
2. $xxAAxxxx$
3. $xxxxAAxx$
4. $xxxxxxAA$

There are $\binom{4}{1}=4$ scenarios with this $1$ pair. As before, all pairs must be considered and there are $4$ pairs. In addition, for each scenario we must consider in how many ways the non-aligned cards can be permutated. The number of ways $3$ pairs can be arranged with $0$ aligned pairs is $A(3,0)$. We don't have a value for this at the moment as we didn't do an example with $n=3$, but I'll get to that. Summing up, we find that $$A(4,1)=\binom{4}{1}*4*A(3,0)$$ which fits the generalized formula I gave in the previous case.

So, we have a generalized formula for the number of aligned pairs in a given arrangement. However, we need to do some "fixes". Firstly, to make it work for $k=n$ we need to define the following: $$A(0,0)=1$$

To make it work for $k=n-1$ we need to define: $$A(n,n-1)=0$$

Lastly, we need to give a general formula for $A(n,0)$. This is the number of arrangements with $n$ pairs where there are no aligned pairs. This can found as the total number of arrangements minus all the arrangements where there is $1$ or more aligned pairs. In other words: $$A(n,0) = TA(n)- \sum_{k=1}^n A(n,k)$$

We can now write the formula for the expected number of turns for $n$ pairs. For all arrangements with $k$ aligned pairs, we must do $k$ flips + $2(n-k)$ flips. The expected number of turns is thus: $$E(n) = \frac{1}{TA(n)}\sum_{k=0}^n A(n,k)(k+2(n-k))$$

As I said, it's not beautiful, but it seems to work.

Answer 3

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.