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?
(In reply to
re(2): computer discovery by Charlie)
Coding for a strategy where you can choose your second card knowing the result of the first within that round:
2 8/3 = 2.66666666666667
3 65/15 = 4.33333333333333
4 622/105 = 5.92380952380952
5 7137/945 = 7.55238095238095
6 95244/10395 = 9.16248196248196
7 1456653/135135 = 10.779242979243
8 25120890/2027025 = 12.3929847929848
9 482692725/34459425 = 14.0075675958029
Comparing with previously mentioned (exceptional) strategy for n=2:
1/3 probability of immediate match and total number of rounds is 2.
If no match on first round (probability 2/3), first card on second round will definitely match one of the first two cards, so there are a total of 3 rounds.
Average is 2.6666...
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
'new code for non-simultaneous flips
If vp = 0 Then ' first choice is the already known value
removals = removals + 1
Mid(kn$, psn(v, 1), 1) = Mid(bd$, psn(v, 1), 1)
aknown = aknown - 1
chos=chos+1 ' making second choice now
End If
End If
chos = chos + 1
If chos = 2 Then Exit For
End If
Next
End If
|
|
Posted by Charlie
on 2017-06-01 10:32:45 |
re(3): computer discovery
