For a positive integer $a$, define a sequence of integers $x_{1}, x_{2}, \ldots$ by letting $x_{1}=a$ and $x_{n+1}=2 x_{n}+1$ for $n \geq 1$. Let $y_{n}=2^{x_{n}}-1$. Determine the largest possible $k$ such that, for some positive integer $a$, the numbers $y_{1}, \ldots, y_{k}$ are all prime.
(Russia) Valery Senderov
The largest such is $k=2$. Notice first that if $y_{i}$ is prime, then $x_{i}$ is prime as well. Actually, if $x_{i}=1$ then $y_{i}=1$ which is not prime, and if $x_{i}=m n$ for integer $m, n>1$ then $2^{m}-1 \mid 2^{x_{i}}-1=y_{i}$, so $y_{i}$ is composite. In particular, if $y_{1}, y_{2}, \ldots, y_{k}$ are primes for some $k \geq 1$ then $a=x_{1}$ is also prime.

Now we claim that for every odd prime $a$ at least one of the numbers $y_{1}, y_{2}, y_{3}$ is composite (and thus $k<3$). Indeed, if $a \equiv 1(\bmod 4)$, then $x_{2} \equiv 3(\bmod 4)$; consequently, $x_{3} \equiv 7$ $(\bmod 8)$. This implies that 2 is a quadratic residue modulo $p=x_{3}$, so $2 \equiv s^{2}(\bmod p)$ for some integer $s$, and hence $2^{x_{2}}=2^{(p-1) / 2} \equiv s^{p-1} \equiv 1(\bmod p)$. This means that $p \mid y_{2}$, thus $2^{x_{2}}-1=x_{3}=2 x_{2}+1$. But it is easy to show that $2^{t}-1>2 t+1$ for all integer $t>3$. A contradiction.

Finally, if $a=2$, then the numbers $y_{1}=3$ and $y_{2}=31$ are primes, while $y_{3}=2^{11}-1$ is divisible by 23 ; in this case we may choose $k=2$ but not $k=3$.

Remark. The fact that $23 \mid 2^{11}-1$ can be shown along the lines in the solution, since 2 is a quadratic residue modulo $x_{4}=23$.