MathDB

B3

Part of 2023 Putnam

Problems(1)

2023 Putnam B3

Source:

12/3/2023
A sequence y1,y2,…,yky_1, y_2, \ldots, y_k of real numbers is called <spanclass=′latex−italic′>zigzag</span><span class='latex-italic'>zigzag</span> if k=1k=1, or if y2−y1,y3−y2,…,yk−yk−1y_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 n≥2n \geq 2.
PutnamPutnam 2023