## The Length of Memory

In the game of Memory, there are many different cards, each having one matching card to make its pair. To start the game, all the cards are spread out face down. On each turn, a player chooses a card and turns it over, then chooses a second card and turns it over. If the cards match, they are removed from the play area. If the cards do not match, they are returned to their face-down positions.
1. Assuming you have perfect memory (you can remember where all previously seen cards are), what is the expected number of turns needed to clear the play area for N pairs?
2. How does this result change if two cards must first be selected, then turned over simultaneously?
3. How does the first result change if there are mulitple identical pairs, such as in a standard deck of cards (any Queen could be paired with any other Queen)?
In all cases, assume you play to minimize the number of turns.

Source: Original.

Solutions were received from several people. There wasn't a simple concensus among them. Some are included below, in order of their arrival, not necessarily in accuracy. [I'll admit I haven't had the time to analyze this myself, yet, so I don't have a solution to add or promote. - KD]

Sandy Thompson wrote a game which simulates this Memory game at: http://www.prevalence.com/games/snowflakes.

From Joe DeVincentis:
```Hmm, this is an interesting problem.

Some assumptions:

Whenever you know the locations of two cards that make up a pair, you
immediately remove them.  For the rest of the strategy, I will assume
you know X different cards, and Y unknown cards remain. Y>=X at all times.

In game #1, begin by picking an unknown card.  If that card matches
another known card, you immediately pick it to remove the pair; otherwise,
you choose another unknown card.  The second card may be another new card,
a match for an existing card, or the match for the first card in this pair.

In game #2, except in certain instances near the end of a game, the best
strategy appears to be to always pick two unknown cards.  In this manner,
you will be guaranteed to need no more than 2N turns to finish the game,
choosing most cards twice over the course of the game -- once to identify
a card, again to remove it once you have identified its mate.  You will
beat the 2N limit only when you are lucky and manage to pick an unknown
matched pair.  There will be N turns in the game when you pick an unknown
card, but your chance of picking a pair on each one depends on X, the
number of known single cards; as X approaches Y, the probability of an
unknown pair matching drops to 0.

Note that even in this situation where X=Y, it is generally advantageous
to pick two unknown cards, rather than taking a chance at making a pair by
choosing a known card and an unknown card.  Picking two unknown cards
identifies those two cards for you and allows you to remove two pairs on
the next two turns, achieving a net result of 2 pairs removed in 3 turns,
while the alternative gives you a 1/X chance of removing a pair right away,
and an (X-1)/X chance of revealing one new card, allowing you to remove
a pair the following turn, for a net result of removing 1 pair in an average
of 1/X + 2*(X-1)/X turns, which is 2 - 1/X, which is more than 1.5 turns
(the average turns per pair from the alternate scheme) for any X > 2.

The odd end-game cases I will examine are ones where you have 6 or fewer
cards left.  Note that 2 cards left is a special case; whether you know
the cards or not, you can clear the table in 1 move.  A normal move can
at most reveal 2 new cards, allowing you to remove 4 cards from the table
with certainty, so I am treating the 4-card and 6-card cases as (possibly)
special.

If you have 6 cards left, you will know either 0 or 2 of them. (Note that
the procedure above ensures you will always know an even number of the
remaining cards at the end of any move, until you make some move contrary to
that general strategy.)  If you know 0, the only move is to pick a random
pair, and you will then either know 2, or get lucky and reach the
4-cards-and-know-0 state.

When you have 6 cards and know 2, if you choose two unknown cards, with
probability 1/6 you will find the matches for both known cards, and in 3
additional turns clear the table.  With probability 1/6, you will choose
the hidden pair and reach the 4-cards-and-know-2 state (in 1 turn).
With probability 2/3, you find a match for one of your known cards, and
one card from the other pair, and be able to make a match on your next
turn, reaching the 4-cards-and-know-2 state in 2 turns.

If you instead begin by choosing one known and one unknown card, then with
probability 1/4 you will make a match, and reach 4-cards-and-know-1 in 1
turn.
With probability 1/4, you will match the other known card, and remove it the
next turn, thus reaching 4-cards-and-know-1 in 2 turns. With probability 1/2
the unknown card you reveal will be a different one, and you thus reach
6-cards-and-know-3 in 1 turn.

Now, consider the cases with 4 cards remaining.  If you know 0, pick any
pair and you will either get a match, clearing the board in 2 turns
(1/3 probability), or you will then know 2 different cards of the 4
(2/3 probability).

>From 4-cards-and-know-2, if you follow the default strategy, you will select
the 2 unknown cards, then know all 4, and in 2 more moves clear the board --
thus always using 3 moves.  If instead you first pick one known and one
unknown card, you will with 1/2 probability pick a pair (and clear the board

in 2 moves) and with 1/2 probability have information to clear the board in
2 more moves (for a total of 3), thus achieving an average of 2.5 moves to
finish the board.  Thus, for 4-cards-and-know-2 it is better to deviate from
the normal strategy.  This also gives us an expectation of
4*1/6 + 3.5*1/6 + 4.5*2/3 = 51/12 = 4.25 turns to clear the
6-cards-and-know-2
state by starting by picking 2 unknown cards.

If you know 1 of the four cards, if you pick it and another for the first
move,
this is the same as if you didn't know any cards initially, which we now
know
takes an average of 2*1/3 + 3.5*2/3 = 9/3 = 3 turns. If you instead pick 2
other
cards, then with probability 1/3 they match and you clear the board in 2
turns,
and with probability 2/3 they differ, but one matches the one you already
knew,
and you clear the board in a total of 3 turns, for an average of
2*1/3 + 3*2/3 = 8/3 turns.

Finally, if you have 6 cards and know 3, if you being by choosing 2 unknown
cards they will never match, but always allow you to clear the board in a
total of 4 turns.  If you choose one known and one unknown, with
probability 1/3 they will match and you will reach 4-cards-and-know-2, but
with
probability 2/3 they will not match, but the new card will match one of the
other known cards, so after 1 more move you will reach 4-cards-and-know-2.
So this method takes, on average, 3.5*1/3 + 4.5*2/3 = 25/6 turns.  Choosing
2 unknown cards is better.

Thus, the strategy of starting with one known and one unknown card from
6-cards-and-know-2 has an expectation of 11/3*1/4 + 14/3*1/4 + 5*1/2 = 55/12
turns,
so the strategy of choosing 2 unknown cards is better for this case too --
thus,
it is best for all the 6-card cases.  The strategy of choosing one known and
one unknown card gets worse and worse as you add more cards, as you have
less
and less chance of getting a match on the first pick, which is the only way
that strategy wins -- in every other case, you know one less card than you
otherwise would.

So, for the general case, you save, on average, a little over half a turn at
the end, due to the special cases with 2 and 4 cards.  (The exact amount
varies
with the probability of reaching 6 cards vs. 4 cards; I'm not going to try
to
calculate this.)  The number of turns saved before the endgame is simply the
number of times a random draw of two unknown cards pulls up a match.  This
is
1/(2N-1) for the first pick, and is reduced as you go along by the
likelihood
of picking cards whose matches are already known.  A rough approximation is
to
assume it goes to zero linearly over the course of the N draws of two
unknown
cards, so we have something like N/(4N-2) or about 1/4 turn saved.  Thus,
the
overall expectation for N cards is about 2N-1 turns.

Now, for game #1, you can save more turns over the above, because when you
choose an unknown card for the first card, if it matches a known card, you
can
make that match immediately, saving a turn.  Actually, you only save half a
turn
on average here, compared to a draw of two random cards, because you lose
the
information from revealing a second card.  Two occurrences of this will save
two
turns, but reveal two fewer cards, so you'll need to spend one of those
turns to
reveal those cards.  One occurrence can save a turn while revealing one less
card,
which may require only a partial turn on average to recover -- for instance,
if
you end up in the 4-cards-and-know-1 state, it only requires 1/6 turn more
on
average than the 4-cards-and-know-2 state you might more commonly end up in.

Furthermore, you are likely to encounter this situation many times, unlike
getting correct random matches in the other game, because you only need to
match that first card against any already known card, as opposed to matching
it
against the one specific unknown card, and the chances of already knowing
where
the matching card is increase as we know more single cards.  The same rough
assumption I used before, assuming that initially we have no known cards and
at
the end we have X=Y, gives an expectation of matches which is something like
N/2,
assuming N times that we pick an unknown card first, but since we sometimes
don't
pick an unknown card as the second card, we will have more of these random
picks -- N/4 more, and this gives another N/8 more matches, and so on...
this is
an infinite series which gives us a sum of 4N/3 unknown cards chosen as the
first
pick, and 2N/3 of these matches, which saves us N/3 turns, so we expect to
take
roughly 5N/3 turns to play the game.  I don't think we still get much of the
other reduction of about one turn in this case, since it depended on the
end-of-game behavior and blind picks of two unknown cards, and we've reduced
the
number of blind picks somewhat, and this estimate assumes we end up in the
X=Y
state at the end, at which we already need just one turn per pair to finish
the
game, because we can match any new card we expose with a known card.

Joseph DeVincentis
devjoe@rcn.com
```

From Dave Bachtel:
```Nothing done mathematically, just tried several different combinations to
arrive at the formula.

I will address question 1 and question three at the same time,

All assuming that the person has perfect memory but very lousy luck, here is
the formula to calculate
the number of turns needed:

Question (3)
N = number of different sets
x  = number of pairs of the different sets

# turns = 2*x*N - N + N/2        for N= even integer

=2*x*N - N + (N+1)/2   for N= odd integer

to solve for question (1)  x=1  so they simplify to

N + N/2  for  N= even
N + (N+1)/2    for N=odd

there are three different areas where the turns need to be
(1)  feel out phase =   find all the different N cards  this is
the N/2 part of the equation
(2)  finding all the pairs minus one set of pairs  this is equal
to (x-1)*2N
(3)  finding the last set of pairs   this is equal to N

Question (2)      # turns = 2*N  when x=1
I did not try to solve question (2) when x>1
I just did several different levels and all of them were equal to 2N.
Half of them are used in getting the pairs turned over
The other half to find the different location of the matches
because the idea is to turn over new cards
every turn until you find a match for the particular N.

David R. Bachtel

Looking at question (2) the person would need to find out all the different
card locations before getting done
so to answer part (b) of the question he would need 2Nx (see below for
description of symbols) turns if
he could only turn two over simultaneously and there were x multiples of
pairs of cards.

Dave Bachtel
```

From Philippe Fondanaiche
```Before trying to calculate the expected numbers, I have  determined what
could be the best strategy to minimize the number of turns. Intuitively but
it's not a demonstration, I propose the following strategy :
Let assume that 2n cards out of the initial 2N cards are still on the play
area and no pair has been previously identified in this set of 2n
cards.Whatever the cards turned up to now, I choose a new card C1 and turn
it. Two cases are possible:
- either a similar card to C1 has been already turned and as I have a
perfect memory, I piece together the 2 cards. In this case, 3 turns are
needed to get a pair.
- or there is no matching card already turned identical to C1 and I choose
again a second new card C2 . Two cases are again possible:
- either the 2 cards C1 and C2 are matched and in this case, 2 turns
only are needed.
- or C2 has its double in the cards already chosen. C1 and C2 are
returned to their face-down positions but at the following turn, I put
together the two matching cards previously identified.In this case, 4 turns
are needed to create a pair.
- or C2 is unique and I continue the process with 2*(n-2) remaining
cards....
Through this algorithm I have got the following formulas which give
satisfactory estimates of the expected numbers:
Question 1: (7*N - 3 ) / 2
Question 2: (15*N - 4) / 4
Question 3 : 7*N - 2 with a deck of 4*N cards

PS The underlying probability law of this problem seems to be particularly
complex to be established.So,the results have been obtained through an
empirical approach. For example, in the first question, there is in average
for N<100, one pair of consecutive and matching cards such the second card is
turned at an even position. The remaining (N-1) pairs are split equally
between the case "3 turns are needed" and the case "4 turns are needed". So
the expected number of turns is equal to 2*1 + 3*(N-1)/2 + 4*(N-1)/2 =
(7*N-3)/2.
```

From Colin Bown 10/11/00:
```Problem #1:

let T(N,M) be the expected number of turns with N Pairs remaining and
M cards known.

T(N,M>=N) = N

Strategy for T(N,M):
Pick one of (2N-M) unseen cards:
M times it matches, remove the pair, T = 1+T(N-1,M-1)
(2N-2M) times it doesn't match: Pick another from remaining (2N-M-1)
1 time it matches and is removed, T = 1 + T(N-1,M)
M times it matches old seen card, remove pair, T = 2 + T(N-1,M)
(2N-2M-1) times no match is found, T = 1 + T(N,M+2)

T(N,M) = 1/(2N-M) (    M    *        ( 1 + T(N-1,M-1) ) +
(2N-2M)/(2N-M-1)*( 1         * (1 + T(N-1,M)) +
M         * (2 + T(N-1,M)) +
(2N-2M-1) * (1 + T(N,M+2)) ) )

Yuck! I can't do this analytically.  10 minutes of programming gives
me an approximate linear asymptotic form of T(N,0) = -2.31 + 1.81 N
there is also a small bimodal structure with odd values of N being
slightly harder to finish than even values.

Colin
```

Mail to Ken