Putnam 2023 
Topic: Combinatorics Probability

Problem: A sequence $y_1,y_2,\dots,y_k$ of real numbers is called \emph{zigzag} if $k=1$, or if $y_2-y_1, y_3-y_2, \dots, y_k-y_{k-1}$ are nonzero and alternate in sign. Let $X_1,X_2,\dots,X_n$ be chosen independently from the uniform distribution on $[0,1]$. Let $a(X_1,X_2,\dots,X_n)$ be the largest value of $k$ for which there exists an increasing sequence of integers $i_1,i_2,\dots,i_k$ such that $X_{i_1},X_{i_2},\dots,X_{i_k}$ is zigzag. Find the expected value of $a(X_1,X_2,\dots,X_n)$ for $n \geq 2$.

Solution: Divide the sequence $X_1,\dots,X_n$ into alternating increasing and decreasing segments, with $N$ segments in all. Note that removing one term cannot increase $N$: if the removed term is interior to some segment then the number remains unchanged, whereas if it separates two segments then one of those decreases in length by 1 (and possibly disappears). From this it follows that $a(X_1,\dots,X_n) = N+1$: in one direction, the endpoints of the segments form a zigzag of length $N+1$; in the other, for any zigzag $X_{i_1},\dots, X_{i_m}$, we can view it as a sequence obtained from $X_1,\dots,X_n$ by removing terms, so its number of segments (which is manifestly $m-1$) cannot exceed $N$.  For $n \geq 3$, $a(X_1,\dots,X_n) - a(X_2,\dots,X_{n})$ is 0 if $X_1, X_2, X_3$ form a monotone sequence and 1 otherwise. Since the six possible orderings of $X_1,X_2,X_3$ are equally likely, \[ \mathbf{E}(a(X_1,\dots,X_n) - a(X_1,\dots,X_{n-1})) = \frac{2}{3}. \] Moreover, we always have $a(X_1, X_2) = 2$ because any sequence of two distinct elements is a zigzag. By linearity of expectation plus induction on $n$, we obtain $\mathbf{E}(a(X_1,\dots,X_n)) = \frac{2n+2}{3}$ as claimed. The expected value is $\boxed{\frac{2n+2}{3}}$.