Strategies in Memory game There's well known Memory game where you have $2n$ cards of $n$ colours face down (it's originally a two-player game, but I'll consider solitaire version). You can $k$ times flip $2$ cards face up and take them if they have same colour, and you obviously want to collect as much as possible. It's pretty obvious that optimal strategy should be like that: flip $c_1(n, k)$ disjoint pairs, then take all $p_1$ pairs you saw, flip $c_2(n, k, p_1)$ more, repeat until you run out of flips. 


*

*What is the (asymptotic for $n \gg 1$) optimal strategy and how does distribution of score look like? Are there some breakpoints for certain ratios $k/n$?

*What about optimal strategy, if goal is to maximize ratio between taken and flipped cards?
 A: The strategy can be much simpler:  take a pair if you know one, otherwise flip two unknown cards.  If you know a pair, you will need to use a flip to take it, so use the flip now.  That makes the analysis much easier.  
Now a position is specified by $n$, the number of pairs remaining, $f$, the number of flips remaining, and $u$, the number of unpaired cards you know.  $u$ is always even.  We only need to consider cases where you don't know any pairs.  From a position $(n,f,u)$ you move to $$\begin {array} {c | c | c} \text{state}&\text{probability}&\text{pairs found}\\ \hline
(n,f-1,u+2)&\frac {(2n-u)(2n-u-2)}{2n(2n-1)}&0\\
(n-1,f-2,u)&\frac {2u(2n-u)+(2n-u)}{2n(2n-1)}&1\\
(n-2,f-3,u-2)&\frac {u(u-1)}{2n(2n-1)}&2 \end {array}$$
where the first line comes from picking two cards that don't match anything you know and don't match each other, the first term in the second line is picking one that matches a known card and one that is unknown, the second term in the second line is picking an unknown card and its match, and the thrid line is picking two known cards. There is a perturbation at the end where you might run out of flips.  If you have only one flip remaining you can't claim any pair you find.
