We are given an integer $n \geq 1$ and $2n$ cards, labelled $0$ to $2n-1$. We pick a card with uniform probability, put it back, and continue, until for some $k\in \{0,n-1\}$ the cards
$2k$ and $2k+1$ have been picked up at least once, in any order. Then we stop and count the number of steps. Let us call the expected value of steps needed to complete the game $E_n$.
Do we have $0 < \lim\inf_{n\to\infty} E_n/\log(n) < \infty$?
Best Answer
$\newcommand{\J}{\mathcal J}$More or less straightforward calculations show that $$E_n=\frac1{(2 n-1)!}\sum _{k=0}^n a_k,$$ where $$a_k:=a_{n,k}:=k! (2 n-k-1)! \binom{2 n-k+1}{k}.$$
This is rather easy to analyze by considering the ratios $a_{k+1}/a_k$, to get $$E_n\asymp\sqrt n,$$ as suggested in the comment by Sam Hopkins (even though I do not understand why this is very close to the birthday problem).
For an illustration, here is the (connected) plot $\{(n,E_n)\colon n=1,\dots,1000\}$:
Thinking a bit more about the comment by Sam Hopkins, now the similarity with the birthday problem seems clearer to me: there, we deal with exact coincidences of birthdays, here with near coincidences of ($2n$)-nomial outcomes.
Details: We do not have to assume that the number of cards, say $m$, is even. Let then $n:=\lfloor(m+1)/2\rfloor$.
Let $\nu_m$ be the number of steps needed to have picked up, at least for some $k$, the neighbor cards labeled $k$ and $k+1$, so that \begin{equation*} E_m:=E\nu_m=\sum_{r=0}^\infty P(\nu_m>r). \tag{1} \end{equation*} Note that \begin{equation*} P(\nu_m>r)=\frac1{m^r}\,\sum_{k\ge0}\,\sum_{J\in\J_{m,k}}S_{k,r} =\frac1{m^r}\,\sum_{k\ge0}|\J_{m,k}| \, S_{k,r}, \tag{2} \end{equation*} where \begin{equation*} \J_{m,k}:=\Big\{J\subseteq[m]\colon|J|=k,\ \sum_{j=0}^{m-1}1(\{j,j+1\}\subseteq J)=0\Big\}, \end{equation*} $[m]:=\{1,\dots,m\}$, $|\cdot|$ denotes the cardinality, and $S_{k,r}$ is the number of maps from $[r]$ onto $[k]$. By inclusion-exclusion, \begin{equation*} S_{k,r}=\sum_{j=0}^k(-1)^j\binom kj (k-j)^r, \end{equation*} with $0^0:=1$.
The set $\J_{m,k}$ is obviously in a one-to-one correspondence with the set (say $Q_{m,k}$) of all sequences in $\{0,1\}^m$ with exactly $k\,$ $1$'s such that between any two subsequent $1$'s there is at least one $0$.
In turn, the set $Q_{m,k}$ is in a one-to-one correspondence with the set (say $R_{m,k}$) of all sequences in $\{0,1\}^{m-(k-1)}$ with exactly $k\,$ $1$'s: a bijection from $Q_{m,k}$ onto $R_{m,k}$ can be obtained by removing one $0$ from between any two subsequent $1$'s.
Thus, $|\J_{m,k}|=|Q_{m,k}|=|R_{m,k}|=\binom{m-k+1}k$ and hence, by (1) and (2), \begin{equation*} \begin{aligned} E_m &=\sum_{k\ge0}\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \sum_{r=0}^\infty\frac{(k-j)^r}{m^r} \\ &=\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \frac m{m-k+j} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \sum_{j=0}^k(-1)^j\binom kj \int_0^1 dx\,x^{m-k+j-1} \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \int_0^1 dx\,x^{m-k-1}(1-x)^k \\ &=m\,\sum_{k=0}^n\binom{m-k+1}k \, \frac{k!(m-k-1)!}{m!} \\ &=\sum_{k=0}^n b_k, \end{aligned} \tag{3} \end{equation*} where \begin{equation*} b_k:=b_{m,k}:=\binom{m-k+1}k\Big/\binom{m-1}k. \end{equation*}
It is easy to see that $b_k$ is decreasing in $k$, with \begin{equation*} \frac{b_{k+1}}{b_k}=1-(1+o(1))\frac kn=\exp\Big\{-(1+o(1))\frac kn\Big\} \end{equation*} if $k=o(n)$. Since $b_0=1$, we have \begin{equation*} b_k=\exp\Big\{-(1+o(1))\frac{k^2}{2n}\Big\} \end{equation*} if $k=o(n)$. Also, since $b_k$ is decreasing in $k$, it follows that $b_k=\exp\big\{-c^2 n/3\big\}$ if $k\ge cn$ and $n$ is large enough, for any fixed $c>0$. Thus, by (3), \begin{equation*} \begin{aligned} E_m &\sim\int_0^n dx\,\exp\Big\{-\frac{x^2}{2n}\,(1+o(1))\Big\} \sim\sqrt{\frac\pi2}\, \sqrt n\approx1.25\,\sqrt n; \end{aligned} \tag{3} \end{equation*} cf. the picture above.