PUMaC 2019 · 团队赛 · 第 13 题
PUMaC 2019 — Team Round — Problem 13
题目详情
- Let e , e , . . . e be independently chosen from the set { 0 , 1 , . . . , 20 } uniformly at random. 1 2 2019 2 π 2019 2 2019 2 i Let ω = e . Determine the expected value of | e ω + e ω + . . . + e ω | . 1 2 2019
解析
- Let e , e , . . . e be independently chosen from the set { 0 , 1 , . . . , 20 } uniformly at random. 1 2 2019 2 π 2019 2 2019 2 i Let ω = e . Determine the expected value of | e ω + e ω + . . . + e ω | 1 2 2019 Proposed by: Frank Lu Answer: 74030 2 2019 2019 First, we know that ω + ω + . . . + ω = 0, since ω 6 = 1 and ω is a root of x − 1 = 0, which 2 2018 2 2019 means that ω is a root of 1 + x + x + . . . + x . But then ω + ω + . . . + ω = 0. Thus, given a choice of e , subtracting 10 from each value of e yields the same value for the quantity i i 2 2019 2 | e ω + e ω + . . . + e ω | (and in fact gives the same complex number). We may thus shift 1 2 2019 the range of the e to be in {− 10 , − 9 , . . . , 9 , 10 } . Now, suppose we are given the first n values i n +1 2 of e , and we get the complex number z . We consider the expected value of | z + e ω | . i n n n +1 We first replace this with just any complex numbers a + bi, c + di for generality. Then, the value 2 2 2 2 2 2 2 of | a + bi + e ( c + di ) | is a + b + e c + e d + 2 ∗ a ∗ c ∗ e + 2 ∗ b ∗ d ∗ e . Given our n +1 n +1 n +1 n +1 n +1 2 2 2 2 2 2 2 possible values for e , this yields us an average of a + b + ∗ (0 + 1 + . . . + 10 )( c + d ). n +1 21 2 10 ∗ 11 ∗ 21 110 But we can calculate the coefficient as ∗ = . Hence, the expected increase in our 21 6 3 110 absolute value due to any term is . We thus see that starting with the value of 0 (starting 3 110 with no terms at all), we get that our final answer is ∗ 2019 = 74030. 3