PUMaC 2021 · 团队赛 · 第 8 题
PUMaC 2021 — Team Round — Problem 8
题目详情
- The new PUMaC tournament hosts 2020 students, numbered by the following set of labels 1 , 2 , . . . , 2020. The students are initially divided up into 20 groups of 101, with each division into groups equally likely. In each of the groups, the contestant with the lowest label wins, and the winners advance to the second round. Out of these 20 students, we chose the champion a uniformly at random. If the expected value of champion’s number can be written as , where b a, b are relatively prime integers, determine a + b .
解析
- The new PUMaC tournament hosts 2020 students, numbered by the following set of labels 1 , 2 , . . . , 2020. The students are initially divided up into 20 groups of 101, with each division into groups equally likely. In each of the groups, the contestant with the lowest label wins, and the winners advance to the second round. Out of these 20 students, we chose the champion a uniformly at random. If the expected value of champion’s number can be written as , where b a, b are relatively prime integers, determine a + b . Proposed by: Frank Lu Answer: 2123 1 First, let S be the sum of the winners. We want to find E ( S ). To find S, we write this as 20 P 2020 iX , where X is equal to 1 if and only if contestant i was the winner of their group, and i i j =1 zero otherwise. Now, note that E ( iX ) is equal to i times the probability that X is equal to 1. i i 2020 − i But P ( X = 1) is the probability that player i is the lowest in their group. There are i 100 2019 possibilities for this, and a total of in total for the group, meaning that our probability 100 2020 − i 2020 − i P i ( ) ( ) 2020 100 100 is just . By linearity of expectation, we find that E ( S ) = . We can in turn 2019 2019 i =1 ( ) ( ) 100 100 2020 − i P P ( ) 2020 i 100 rewrite this sum as equalling E ( S ) = . By changing the order of summation 2019 i =1 j =1 ( ) 100 2020 − i 2021 − j P P P ( ) ( ) 2020 2020 2020 100 101 and using hockey-stick identity, this is equal to = , which 2019 2019 j =1 i = j j =1 ( ) ( ) 100 100 2021 ( ) 102 2021 · 2020 in turn is with another application of hockey-stick. We thus see that E ( S ) = , 2019 102 · 101 ( ) 100 2021 · 2020 which means that our desired expected value is equal to , giving us our total expected 102 · 101 · 20 3 2021 value of , which we can see is relatively prime as 2021 is not divisible by any of 2 , 3 , 17 102 and thus yielding the answer of 2123.