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?
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 turns
2 4 20/6 = 3.33333333333333
3 6 486/90 = 5.4
4 8 18720/2520 = 7.42857142857143
5 10 1071000/113400 = 9.44444444444444
6 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$
Private Sub Form_Load()
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()
Private Sub Form_Load()
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"
addOn
Text1.Text = Text1.Text & n & " " & totchoices & "/" & trials & " = " & totchoices / trials & crlf
Next n
End Sub
Sub addOn()
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
addOn
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 |
computer discovery
