HMMT 二月 2023 · 冲刺赛 · 第 25 题
HMMT February 2023 — Guts Round — Problem 25
题目详情
- [20] The spikiness of a sequence a , a , . . . , a of at least two real numbers is the sum | a − a | . 1 2 n i +1 i i =1 Suppose x , x , . . . , x are chosen uniformly and randomly from the interval [0 , 1]. Let M be the largest 1 2 9 possible value of the spikiness of a permutation of x , x , . . . , x . Compute the expected value of M . 1 2 9 ◦ ◦ 2
解析
- [20] The spikiness of a sequence a , a , . . . , a of at least two real numbers is the sum | a − a | . 1 2 n i +1 i i =1 Suppose x , x , . . . , x are chosen uniformly and randomly from the interval [0 , 1]. Let M be the largest 1 2 9 possible value of the spikiness of a permutation of x , x , . . . , x . Compute the expected value of M . 1 2 9 Proposed by: Gabriel Wu 79 Answer: 20 Solution: Our job is to arrange the nine numbers in a way that maximizes the spikiness. Let an element be a peak if it is higher than its neighbor(s) and a valley if it is lower than its neighbor(s). It is not hard to show that an optimal arrangement has every element either a peak or a valley (if you have some number that is neither, just move it to the end to increase spikiness). Since 9 is odd, there are two possibilities: the end points are either both peaks or both valleys. Sort the numbers from least to greatest: x , . . . , x . If we arrange them in such a way that it starts 1 9 and ends with peaks, the factor of x added to the final result will be [ − 2 , − 2 , − 2 , − 2 , 1 , 1 , 2 , 2 , 2], respec- i tively. If we choose the other way (starting and ending with valleys), we get [ − 2 , − 2 , − 2 , − 1 , − 1 , 2 , 2 , 2 , 2]. Notice that both cases have a base value of [ − 2 , − 2 , − 2 , − 1 , 0 , 1 , 2 , 2 , 2], but then we add on max( x − 6 i 2 4 6 2 x , x − x ). Since the expected value of x is , our answer is − (1 + 2 + 3) − + + (7 + 8 + 5 5 4 i 10 10 10 10 10 3 3 2