HMMT 十一月 2016 · 冲刺赛 · 第 28 题
HMMT November 2016 — Guts Round — Problem 28
题目详情
- [ 15 ] The numbers 1 − 10 are written in a circle randomly. Find the expected number of numbers which are at least 2 larger than an adjacent number.
解析
- [ 15 ] The numbers 1 − 10 are written in a circle randomly. Find the expected number of numbers which are at least 2 larger than an adjacent number. Proposed by: Shyam Narayanan 17 Answer: 3 For 1 ≤ i ≤ 10, let X be the random variable that is 1 if the i in the circle is at least 2 larger than i one of its neighbors, and 0 otherwise. The random variable representing number of numbers that are at least 2 larger than one of their neighbors is then just X + X + · · · + X . The expected value 1 2 10 E [ X + X + · · · + X ] is equal to E [ X ] + E [ X ] + · · · + E [ X ] by the linearity of expectation, so it 1 2 10 1 2 10 suffices to compute E [ X ] for all 1 ≤ i ≤ 10. i By the definition of expected value, E [ X ] = 1 · P (the i is at least 2 larger than one of its neighbors)+0 · i P (it is not at least 2 larger than either of its neighbors) = P (the i is at least 2 larger than one of its neighbors) = 1 − P (the i is at most 1 larger than both of its neighbors). For the last probability, i ’s neighbors must be drawn from the set { max(1 , i − 1) , max(1 , i − 1) + 1 , . . . , 10 } , excluding i itself. This set has ( ) 10 − max(1 ,i − 1) 10 − max(1 , i − 1) elements, so there are a total of sets of two neighbors for i that 2 ( ) 9 satisfy the condition, out of a total of possible sets of two neighbors from all of the numbers that 2 10 − max(1 ,i − 1) 10 − max(1 ,i − 1) ( ) ( ) 2 2 are not i . The last probability is then , so E [ X ] = 1 − . 9 i 9 ( ) ( ) 2 2 9 9 8 7 1 ( ) ( ) ( ) ( ) ( ) 2 2 2 2 2 The final sum we wish to calculate then becomes (1 − )+(1 − )+(1 − )+(1 − )+ · · · +(1 − ) = 9 9 9 9 9 ( ) ( ) ( ) ( ) ( ) 2 2 2 2 2 17 28 21 0 + 0 + (1 − ) + (1 − ) + · · · + (1 − 0) = . 36 36 3