10
$\begingroup$

Suppose we have a game with $2n$ cards labeled $1,1,2,2,...,n,n$, such that for every integer $i$ where $1\leq i\leq n$ we have 2 cards labeled with $i$. Initially, all the cards are placed face-down on a table. Every turn, the player flips over 2 cards one at a time. If they match, which is if the two cards share the same number, the two cards are removed from the board. If they do not match, the two cards are flipped back to their face-down position. The game ends when all pairs have been found, and all the cards have been removed from the table. (This game is known as Concentration).

Assume the player has perfect memory, and that even after flipping a card back over, they are able to remember which card has what number on it. My question is: what is the expected number of turns to complete a game given $n$ starting pairs?

I have thought about this problem, and have come up with a few observations. Let $E(N,k)$ represent the expected number of moves to win from a state with $2N$ total face-down cards ($N$ unfound pairs) remaining and $k$ face-down cards that the player knows the value of.

  • No matter what, we have $k\leq N$, since by PHP, $k>N$ implies that there are at least 2 face-down cards that share a value and where the player knows both their locations. Then the next move would be to flip all these "known" face-down pairs until $k\leq N$ again.
  • $E(N,k)=\frac{k}{2N-k}(E(N-1,k-1)+1)+\frac{2N-2k}{2N-k}\cdot\frac{1}{2N-k-1}(E(N-1,k)+1)+\frac{2N-2k}{2N-k}\cdot\frac{2N-2k-2}{2N-k-1}(E(N,k+2)+1)+\frac{2N-2k}{2N-k}\cdot\frac{k}{2N-k-1}(E(N-1,k)+2)$
  • $E(N,N)=N$
  • $0\leq a<b\leq N\implies E(N,a)>E(N,b)$
  • $\lim_{N\to\infty} E(N,0)-E(N,k)=\frac{k}{2}$
  • $\lim_{N\to\infty} E(N,N-k)-E(N,N)=k$
  • There exists some constant $X$ such that $\lim_{N\to\infty} E(N,0)=X\cdot N$.

If I am not mistaken, the goal to find the expected number of turns to complete a game with $n$ starting pairs reduces to finding that constant $X$. However, I am stuck here. I know $\frac{3}{2}<X<\frac{1+\sqrt{5}}{2}$, but not much more.

$\endgroup$
4
  • 1
    $\begingroup$ I wrote some code, and can conclude that most likely, $1.613585<X<1.613705641$. It's more likely closer to the upper bound, as the lower bound was calculated from $E(i,0)/i$ and the upper bound from $E(i,0)-E(i-1,0)$. $\endgroup$
    – Tracy Morgan
    Jul 6 at 8:29
  • $\begingroup$ Is it true that when $n$ is even best case : n turns , worst case : $ n/2 + n$ turns ? $\endgroup$
    – C.C
    Jul 6 at 10:07
  • $\begingroup$ I was about to answer the question, then discovered this. math.stackexchange.com/questions/1876467/… $\endgroup$
    – YJT
    Jul 6 at 10:24
  • $\begingroup$ @C.C I'm fairly certain the worst case is $2n-1$ and the best case is $n$ for all $n$. $\endgroup$
    – Tracy Morgan
    Jul 7 at 6:13

1 Answer 1

Reset to default
6
$\begingroup$

Wikipedia gives a link to the solution of your question, assuming perfect memorization and an optimal strategy.

The solution is in Daniel J. Velleman; Gregory S. Warrington (2013). "What to Expect in a Game of Memory". The American Mathematical Monthly. Volume 120, Issue 9, pages 787-805 and it is:

$$E(N,0) \approx (3 − 2\ln{2})N + 7/8 − 2\ln{2}$$

therefore:

$$X=3 − 2\ln{2} \approx 1.61370563888$$

A freely accessible previous version of the same work by the same authors, with a different title, can be found at arXiv "Matching expectations".

$\endgroup$
3
  • 2
    $\begingroup$ For the interested: from the arxiv paper, the error on the quoted formula for $E(N,0)$ is $O(1/\sqrt{N})$ $\endgroup$
    – Joshua Lin
    Jul 6 at 14:32
  • $\begingroup$ Wow, didn't see this paper. Now I wonder if some paper exists discussing the win probability of the player that moves first in a 2-player game with $n$ starting pairs. $\endgroup$
    – Tracy Morgan
    Jul 6 at 19:26
  • 1
    $\begingroup$ @TracyMorgan you can take a look at the references at OEIS A299908. I didn't study them, but maybe you can find something useful there. $\endgroup$
    – BillyJoe
    Jul 7 at 5:51

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.