 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Memory Match Game (Posted on 2017-05-31) 10 cards with identical backs are face down on a table. Each card face matches exactly one of the other card faces. The cards are in a random sequence. A turn consists of choosing 2 cards, simultaneously reversing them so that they are face up, discarding them if they match, and turning them face down if they do not match. The game ends when all cards are discarded.

a) If you have perfect memory, and an efficient strategy, then what is the expected number of turns in the 10 card game?

b) What is the expected number of turns if instead there are 2n cards in the starting tableaux, with each card matching exactly one other?

 See The Solution Submitted by Steve Herman No Rating Comments: ( Back to comment list | You must be logged in to post comments.) computer discovery | Comment 1 of 9
The following is based on the strategy of going for previously unexposed cards unless two previously exposed cards match, in which case, choose them.  The order in which the cards are sorted determines the sequence they will be selected as they are selected left to right following the rules of choice.

The ten card game: n = 5 in the below table, so the expected value is 9 + 4/9.

For various n:

`n   cards   expected turns2     4    20/6 = 3.333333333333333     6    486/90 = 5.44     8    18720/2520 = 7.428571428571435    10    1071000/113400 = 9.444444444444446    12    85730400/7484400 = 11.4545454545455`

The pattern seems to be the expected turns =
(2*n-1) + (n-1)/(2*n-1)

The case for n=7 was done with a variation of the program, that used only combinations starting with 1, as the identity of the individual types does not matter:

7  1309770000/97297200 = 13.4615384615385

The expected number of rounds is indeed 13 + 6/13.

A third variation of the program, using only combinations where the first item is 1, and each successive newly found item is the next numerically, such as 1213324554, speeding things considerably, finds

8  31351320/2027025 = 15.4666666666667
9  602026425/34459425 = 17.4705882352941

The table is from:

DefDbl A-Z
Dim crlf\$

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

For n = 2 To 6: ntimes2 = 2 * n

totchoices = 0
DoEvents
Tr = 0
bd0\$ = "112233445566"
bd0\$ = Left(bd0, ntimes2)
h\$ = bd0\$
trials = 0
Do
If bd0\$ = "1122334545" Then
xx = xx
End If
bd\$ = bd0\$
kn\$ = String\$(ntimes2, " ")
ReDim psn(n, 2)
mvs = 0
removals = 0
aknown = 0
trials = trials + 1
choices = 0
Do
DoEvents
p\$ = l\$       ' just for debugging permutations
l\$ = Left\$(bd\$, 9)  'just for debugging permutations
choices = choices + 1
'If l\$ <> p\$ Then Text1.Text = Text1.Text & bd\$ & crlf
If aknown Then
For i = 1 To n
If psn(i, 2) > 0 And psn(i, 0) = 0 Then
p1 = psn(i, 1)
p2 = psn(i, 2)
removals = removals + 1
psn(i, 0) = 1
aknown = aknown - 1
Exit For
End If
Next
Else
chos = 0
vp = 0
v = 0
For i = 1 To ntimes2
If Mid\$(kn\$, i, 1) = " " Then
Mid\$(kn\$, i, 1) = Mid\$(bd\$, i, 1)
vp = v
v = Val(Mid\$(kn\$, i, 1))
If vp = v Then
removals = removals + 1
psn(v, 0) = 1
aknown = aknown - 1  'subtracting before adding this time
End If
If psn(v, 1) = 0 Then
psn(v, 1) = i
Else
psn(v, 2) = i
aknown = aknown + 1
End If
chos = chos + 1
If chos = 2 Then Exit For
End If
Next
End If
Loop Until removals = n
totchoices = totchoices + choices
permute bd0\$
Loop Until bd0\$ = h\$

Text1.Text = Text1.Text & n & "  " & totchoices & "/" & trials & " = " & totchoices / trials & crlf

Next n
End Sub

Latest, fastest, version (labels are such that first appearances are in numeric order) :

DefDbl A-Z
Dim crlf\$, choices, trials, bd0\$, n, totchoices, numOf()

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

For n = 3 To 9
totchoices = 0
DoEvents
trials = 0: totchoices = 0
ReDim numOf(n)
numOf(1) = 1
bd0\$ = "1"
Text1.Text = Text1.Text & n & "  " & totchoices & "/" & trials & " = " & totchoices / trials & crlf

Next n

End Sub

If Len(bd0\$) = 2 * n Then
findchoices bd0\$, n
totchoices = totchoices + choices
Else
For i = 1 To n
If numOf(i) < 2 Then
If numOf(i) > 0 Or didzero = 0 Then
If numOf(i) = 0 Then didzero = i
bd0\$ = bd0\$ + LTrim(Str(i))
numOf(i) = numOf(i) + 1

numOf(i) = numOf(i) - 1
bd0\$ = Left(bd0\$, Len(bd0\$) - 1)
End If
End If
Next
End If
End Sub

Sub findchoices(bd\$, n)
ntimes2 = 2 * n
kn\$ = String\$(ntimes2, " ")
ReDim psn(n, 2)
mvs = 0
removals = 0
aknown = 0
trials = trials + 1
choices = 0
Do
DoEvents
p\$ = l\$       ' just for debugging permutations
l\$ = Left\$(bd\$, 9)  'just for debugging permutations
choices = choices + 1
'If l\$ <> p\$ Then Text1.Text = Text1.Text & bd\$ & crlf
If aknown Then
For i = 1 To n
If psn(i, 2) > 0 And psn(i, 0) = 0 Then
p1 = psn(i, 1)
p2 = psn(i, 2)
removals = removals + 1
psn(i, 0) = 1
aknown = aknown - 1
Exit For
End If
Next
Else
chos = 0
vp = 0
v = 0
For i = 1 To ntimes2
If Mid\$(kn\$, i, 1) = " " Then
Mid\$(kn\$, i, 1) = Mid\$(bd\$, i, 1)
vp = v
v = Val(Mid\$(kn\$, i, 1))
If vp = v Then
removals = removals + 1
psn(v, 0) = 1
aknown = aknown - 1  'subtracting before adding this time
End If
If psn(v, 1) = 0 Then
psn(v, 1) = i
Else
psn(v, 2) = i
aknown = aknown + 1
End If
chos = chos + 1
If chos = 2 Then Exit For
End If
Next
End If
Loop Until removals = n

End Sub

 Posted by Charlie on 2017-05-31 16:20:20 Please log in:

 Search: Search body:
Forums (0)