MathDB
2023 Putnam B3

Source:

December 3, 2023
PutnamPutnam 2023

Problem Statement

A sequence y1,y2,,yky_1, y_2, \ldots, y_k of real numbers is called <spanclass=latexitalic>zigzag</span><span class='latex-italic'>zigzag</span> if k=1k=1, or if y2y1,y3y2,,ykyk1y_2-y_1, y_3-y_2, \ldots, y_k-y_{k-1} are nonzero and alternate in sign. Let X1,X2,,XnX_1, X_2, \ldots, X_n be chosen independently from the uniform distribution on [0,1][0,1]. Let a(X1,X2,,Xn)a\left(X_1, X_2, \ldots, X_n\right) be the largest value of kk for which there exists an increasing sequence of integers i1,i2,,iki_1, i_2, \ldots, i_k such that Xi1,Xi2,XikX_{i_1}, X_{i_2}, \ldots X_{i_k} is zigzag. Find the expected value of a(X1,X2,,Xn)a\left(X_1, X_2, \ldots, X_n\right) for n2n \geq 2.