Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned match. If so he will choose such a pair, turn them and get a pair. If not he will turn uniformly at random a card which has not yet been turned. Then if the corresponding match has turned already he will turn that card and get a pair. If not he will again turn uniformly at random a card which has not yet been turned. As usual if a player gets a pair he can continue. Player A will start. For which $n$ does Player A have an advantage by being able to start and for which $n$ is it actually a disadvantage?

Here is what I considered so far: If $E_{k,l}$ denotes the expected number of pairs the starting player will get when $k$ cards are known and $l\geq k$ cards are unknown one can derive the following recursion formula

$$ E_{k,l}=\frac{k}{l} \left( E_{k-1,l-1}+1 \right)\\ +\frac{(l-k)}{l} \frac{1}{(l-1)} \left( E_{k,l-2}+1 \right)\\ +\frac{(l-k)}{l} \frac{k}{(l-1)} \left( \frac{k+l}{2}-1-E_{k,l-2} \right)\\ +\frac{(l-k)}{l} \frac{(l-k-1)}{(l-1)} \left( \frac{k+l}{2}-E_{k+2,l-2}\right). $$ Furthermore we have $E_{k,k}=k$. The expected number of pairs players $A$ resp. $B$ will get are $E_{0,2n}$ resp. $n-E_{0,2n}$. The following list show the expected number of pairs for A and B for $n\leq 24$.

It seems that for larger $n$ the expected number of pairs for $A$ and $B$ are closer together. Can this be proven rigorously? For $n=18$ the expected number of pairs of $A$ and $B$ are equal and the game is fair in some sense. Do there exist other numbers $n$ with that property? Is it possible to give a characterization of the numbers for which $A$ has an advantage?

A has an advantage for $n\in \{ 1,4,7,8,10,11,14,17,18,20,21,23,24,\dots\}$.

B has an advantage for $n\in \{ 2,3,5,6,12,13,15,16,19,22,\dots\}$

Octave code:

n=50; A=diag(0:n-1);A(1,3)=1;

for s=4:2:n-1 for l=s/2+1:s k=s-l; if k>0 A(k+1,l+1)=k/l*(1+A(k,l)); end if l>k A(k+1,l+1)=A(k+1,l+1)-(l-k)/l*k/(l-1)

A(k+2,l); end if l>k+1 A(k+1,l+1)=A(k+1,l+1)-(l-k)/l(l-k-2)/(l-1)A(k+3,l-1); end if l>k && l>2 A(k+1,l+1)=A(k+1,l+1)+(l-k)/l/(l-1)(1+A(k+1,l-1)); end end end B=zeros(n/2-1,3); for i=1:n/2-1 B(i,:)=[i (i+A(1,2*i+1))/2 (i-A(1,2*i+1))/2]; disp([num2str(i) ':' num2str(A(1,2*i+1)) ' ' num2str((i+A(1,2*i+1))/2)]); endB(:,1) rats(B(:,2)) rats(B(:,3))

Awins=''; Bwins=''; for i=1:n/2-1 if A(1,2*i+1)>0 Awins=[Awins ',' num2str(i)]; else Bwins=[Bwins ',' num2str(i)]; end end Awins Bwins