About problem A4 2022 of Putnam I'm not passing the William Lowell Putnam competition (I live in France) but I'm still fascinated by some of the problems.
This year the A4 problem challenged me and I wanna know your thoughts about it :

Suppose $X_1, X_2, \dots$ real numbers between $0$ and $1$ that are chosen independently and uniformly at random.
Let $S = \displaystyle\sum\limits_{i=1}^k \frac{X_i}{2^i}$ where $k$ is the least positive integer such that $X_k < X_{k+1}$ or $k=\infty$ if there is no such integer.
Find the expected value of $S$.

1 - Is this a classic problem that Putnam competitors know ?
2 - What's the idea to solve this ?
Instictively I would say that :
$$\mathbb{E}[S] = \mathbb{E}\left[ \displaystyle\sum\limits_{i=1}^k \frac{X_i}{2^i} \right] = \displaystyle\sum\limits_{i=1}^k \frac{\mathbb{E}[X_i]}{2^i} = \displaystyle\frac{\mathbb{E}[X_1]}{2} + \displaystyle\frac{\mathbb{E}[X_2]}{4} + \dots + \displaystyle\frac{\mathbb{E}[X_k]}{2^k}$$
And then calculate $\mathbb{E}[X_k]$ for all $k \in \mathbb{N}^*$ but maybe that's not the right idea and the solution is far more exotic.
 A: The probability that $X_1>\cdots>X_n\ge t$ is $\frac{1}{(n-1)!}(1-t)^{n-1}$
$$E(X_n)=\int_0^1 \frac{1}{(n-1)!}t(1-t)^{n-1}dt=\frac{1}{(n-1)!}B(2, n)=\frac{1}{(n+1)!}$$
$$E[S]=\sum_{i=1}^{\infty} \frac{1}{2^{i}}E(X_i)= \frac{1}{2^{i}(i+1)!}=2\sum_{i=2}^{\infty} \frac{1}{2^{i}i!}=2\left(e^{1/2}-1-\frac{1}{2^{1}\cdot 1!}\right)=2e^{\frac{1}{2}}-3$$
by Taylor series $$e^{\frac{x}{2}}=\sum_{n=0}^{\infty} \frac{1}{n!2^n}x^n$$
A: Note that $k = \inf\{j \ge 1 : X_j < X_{j+1} \}$ is random itself (i.e $k(\omega) = \inf\{j \ge 1 : X_j(\omega) < X_{j+1}(\omega)\}$, hence you cannot write something like $\mathbb E[\sum_{j=1}^k "something"] = \sum_{j=1}^k \mathbb E["something"]$ because then the left hand side is deterministic (as an expected value of something), whereas the right hand side remains random (due to the randomness of $k=k(\omega)$).
Note that when $k=k(\omega)$ is some fixed value, then $X_1(\omega) \ge X_2(\omega) \ge ... \ge X_k(\omega)$ and $X_k(\omega) < X_{k+1}(\omega)$. In other words, on the set $\{\omega : k(\omega) = N\}$, your random variables $X_1,...,X_N$ are in non-increasing order, whereas the last one we are focused on, that is, $X_{N+1}$, is greater than $X_N$. Similarly, on the set $\{\omega : k(\omega) \ge N\}$ you just need to have $X_1 \ge ... \ge X_N$.
Let $1_A$ be the indicator (characteristic function) of the set $A$. Note that by Fubinii's theorem, $$ \mathbb E[S] = \mathbb E[\sum_{N=1}^\infty\sum_{j=1}^N \frac{X_j}{2^j} 1_{\{k = N\}}] = \sum_{N=1}^\infty \sum_{j=1}^N \frac{1}{2^j}\mathbb E[X_j 1_{\{k = N\}}] = \sum_{j=1}^\infty \frac{1}{2^j} \sum_{N=j}^\infty \mathbb E[X_j 1_{\{k=N\}}] = \sum_{j=1}^\infty \frac{1}{2^j}\mathbb E[X_j 1_{\{k \ge j\}}].  $$ Hence, we're left with calculating $\mathbb E[X_j 1_{\{k \ge j\}}]$. By the conditional expectation, $$ \mathbb E[X_j 1_{\{k \ge j\}}] = \mathbb E[ \mathbb E[X_j 1_{\{ k \ge j\}} | X_j]] = \mathbb E[X_j  \mathbb E[1_{\{k \ge j\}} | X_j] ]. $$ The inner expectation $\mathbb E[1_{k \ge j} |X_j] = \mathbb P(k \ge j | X_j)$ boils down to calculating the probability that $X_1 \ge X_2 \ge ... \ge X_{j-1} \ge X_j$ (where $X_j$ is some fixed value, due to independence), hence $\mathbb P(k \ge j|X_j) = \frac{(1-X_j)^{j-1}}{(j-1)!} $. Plugging this inside, $$\mathbb E[X_j 1_{\{k \ge j\}}] = \frac{1}{(j-1)!}\mathbb E[X_j (1-X_j)^{j-1}] = \frac{1}{(j-1)!}\mathbb E[X^{j-1} - X^j] = \frac{\frac{1}{j} - \frac{1}{j+1}}{(j-1)!} = \frac{1}{(j+1)!}. $$ (We've used the fact that $X_j \sim 1-X_j$ to avoid calculating some beta integral). Hence $$ \mathbb E[S] = \sum_{j=1}^\infty \frac{1}{2^j} \frac{1}{(j+1)!} = 2\left( \sum_{j=0}^\infty \frac{1}{2^jj!} - 1 - \frac{1}{2}\right) = 2e^{\frac{1}{2}} - 3.$$
