2024 Putnam B4

Let $n$ be a positive integer. Set $a_{n,0} = 1$. For $k \geq 0$, choose an integer $m_{n,k}$ uniformly at random from the set $\{1,\dots,n\}$, and let

$$

a_{n,k+1} = \begin{cases} a_{n,k} + 1, & \mbox{if $m_{n,k} > a_{n,k};$} \\

a_{n,k}, & \mbox{if $m_{n,k} = a_{n,k}$;} \\

a_{n,k}-1, & \mbox{if $m_{n,k} < a_{n,k}$.}

\end{cases}

$$

Let $E(n)$ be the expected value of $a_{n,n}$. Determine $\lim_{n\to \infty} E(n)/n$.

令 $n$ 为正整数。设置 $a_{n,0} = 1$。对于 $k \geq 0$，从集合 $\{1,\dots,n\}$ 中均匀随机选择一个整数 $m_{n,k}$，并让

$$

a_{n,k+1} = \begin{cases} a_{n,k} + 1, & \mbox{if $m_{n,k} > a_{n,k};$} \\

a_{n,k}, & \mbox{如果 $m_{n,k} = a_{n,k}$;} \\

a_{n,k}-1, & \mbox{如果 $m_{n,k} < a_{n,k}$.}

\结束{案例}

$$

令 $E(n)$ 为 $a_{n,n}$ 的期望值。确定 $\lim_{n\to \infty} E(n)/n$。