Source: Original.
Sandy Thompson wrote a game which simulates this Memory game at: http://www.prevalence.com/games/snowflakes.
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. More about this game later. 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
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
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.
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