HMMT 二月 2023 · COMB 赛 · 第 9 题
HMMT February 2023 — COMB Round — Problem 9
题目详情
- There are 100 people standing in a line from left to right. Half of them are randomly chosen to face ( ) 100 right (with all possible choices being equally likely), and the others face left. Then, while there 50 is a pair of people who are facing each other and have no one between them, the leftmost such pair leaves the line. Compute the expected number of people remaining once this process terminates.
解析
- There are 100 people standing in a line from left to right. Half of them are randomly chosen to face ( ) 100 right (with all possible choices being equally likely), and the others face left. Then, while there 50 is a pair of people who are facing each other and have no one between them, the leftmost such pair leaves the line. Compute the expected number of people remaining once this process terminates. Proposed by: Albert Wang 100 2 ( ) Answer: − 1 100 50 Solution: Notice that the order in which the people leave the line is irrelevant. Give each right-facing person a weight of 1, and each left-facing person a weight of − 1. We claim the answer for some arrangement of these 2 n people is − 2 times the minimum prefix sum. For instance: LRRLRLLLRRRRL → ( − 2)( − 2) → 4 RRRLLRLLLRRL → ( − 2)( − 1) → 2 Proof. he final configuration is always of the form LL ...LL RR ...RR ︸ ︷︷ ︸ ︸ ︷︷ ︸ k k and the minimum prefix sum is invariant. As the final configuration has minimum prefix sum is k , we are done. So, we want to find the expected value of the minimum prefix sum across all such strings of 1s and − 1s. To find this, we will instead compute the equivalent value ∞ ∑ Pr[maximum prefix sum is ≥ k ] . k =1 Consider the k th term of this sum, and the corresponding walk from (0 , 0) to (2 n, 0) with L corre- sponding to a step of (1 , − 1) and R corresponding to a step of (1 , 1). Consider the point P at y = k with minimal x -coordinate, and reflect the remainder of the walk across y = k . This gives a path that ends at (2 n, 2 k ). Noting that this is a bijection between walks from (0 , 0) to (2 n, 2 k ) and walks that reach y = k , we have ( ) 2 n ∞ ∞ ∑ ∑ n − k ( ) Pr[maximum prefix sum is ≥ k ] = 2 n n k =1 k =1 [( ) ] ( ) 2 n ∞ ∑ 1 n − k = ( ) − 1 2 n 2 n k = −∞ ( ) 2 n 1 2 ( ) = − 1 . 2 n 2 n 100 2 Adjusting for the factor of 2 we saved at the beginning, our final answer for n = 50 is − 1. 100 ( ) 50