10
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ Jens pointed out an error in my answer, but I fixed it. $\endgroup$ – AlgorithmsX Jul 31 '16 at 20:41
  • $\begingroup$ I made an error somewhere. I would consider mixing Jens's answer with the basic ideas in mine to see if there is a faster way to calculate Jens's answer. $\endgroup$ – AlgorithmsX Jul 31 '16 at 22:34
  • $\begingroup$ I found a closed form solution to this problem, but I have no idea how to prove it. $\endgroup$ – AlgorithmsX Jul 31 '16 at 23:07
  • 2
    $\begingroup$ When you flip over two cards, are you allowed to flip them over one at a time, or must you flip two at once? $\endgroup$ – Marcus Andrews Jul 31 '16 at 23:09
  • $\begingroup$ @MarcusStuhr sorry for the ambiguity! I decided to post that adjustment as a new question. I originally was thinking one at a time, but it seems most read the question as flip two at once, so I've clarified that that is the rule for this question $\endgroup$ – Steve Ladavich Aug 1 '16 at 1:36
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Steve Ladavich - Some problems with this. It doesn't fully answer the question but more importantly, it cannot be right. Take the case $n=2$. This gives $4$ cards which can be arranged in a row in $6$ different ways. If cards are flipped starting at the beginning of a row, then in $2$ cases, only $2$ flips are necessary. In the other $4$ cases, $4$ flips are necessary. This gives an expected number of turns of $\frac{10}{3}$. This doesn't fit at all with the formula above. $\endgroup$ – Jens Jul 31 '16 at 19:45
  • $\begingroup$ @Jens Fixed it. $\endgroup$ – AlgorithmsX Jul 31 '16 at 20:36
  • $\begingroup$ @Jens I forgot that if you find all but one match, the last cards will be a match and that the order in which picking the match is irrelevant. $\endgroup$ – AlgorithmsX Jul 31 '16 at 20:43
  • $\begingroup$ It is not optimal to flip the last two cards in phase 1, unless you can infer from the previous results that they are in fact a match. If they are not a macth 8and you can infer that) there are exactly two cards in what you have already uncovered and do not know the partner of (cause the partners are in the last two cards). So if you flip one of those orphans and one of the last two cards, you have a 50% chance of getting a match while still learning all about the last two cards (even the not flipped one) $\endgroup$ – Hagen von Eitzen Jul 31 '16 at 20:46
  • 1
    $\begingroup$ Of the 90 possible permutations of 3 pairs, there are 6 with 3 aligned pairs, 0 with 2 aligned pairs, 36 with 1 aligned pair and 48 with no aligned pair. An "aligned" pair is a pair that you would flip in the first stage if you started from the beginning of a row of cards. With 3 aligned pairs you only need 3 flips. With 1 aligned pair you need 5. With no aligned pair you need 6. $\endgroup$ – Jens Jul 31 '16 at 22:16
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice strategy - I think I'll have to update the question to explicitly state you can look at the first card before turning over the second. I think this is even better than you've worked out too. Isn't it a (1/2), not (1/3), chance that get a match on the second turn? With 4 cards total, given that the 1st isn't a match, your 2nd flip on turn 2, you choose from 2 cards not 3, so you get... (1/3)*2+(1/2)*3+(1/6)*4 = (17/6) turns on average. $\endgroup$ – Steve Ladavich Aug 1 '16 at 0:43
  • $\begingroup$ I was assuming you couldn't look at the first card before turning the second. If you can, on the second turn (assuming no match on the first turn) you turn a new card first and can be sure of a match. Now it is $\frac 13$ to use two turns and $\frac 23$ to use three, for an average of $2\frac 23$ $\endgroup$ – Ross Millikan Aug 1 '16 at 1:09
  • $\begingroup$ If you can look at the first card before turning the second, the average number of pairs in the first run increases dramatically. In fact the strategy should always be to turn a new card first, then match it if possible, otherwise turn another new card. $\endgroup$ – Ross Millikan Aug 1 '16 at 1:11
  • $\begingroup$ Somehow misunderstood your original answer as leveraging that you CAN look at your first card when in reality it makes no such assumption. Worried I'm bungling this question too much so I'm just going to post the rule adjustment as a second question. $\endgroup$ – Steve Ladavich Aug 1 '16 at 1:27
  • $\begingroup$ I agree that this question assumed you could not look at the first card before choosing the second. The questions are rather different, so I think they should be asked separately. $\endgroup$ – Ross Millikan Aug 1 '16 at 3:46
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.