HMMT 二月 2022 · COMB 赛 · 第 8 题
HMMT February 2022 — COMB Round — Problem 8
题目详情
- Random sequences a , a , . . . and b , b , . . . are chosen so that every element in each sequence is chosen 1 2 1 2 independently and uniformly from the set { 0 , 1 , 2 , 3 , . . . , 100 } . Compute the expected value of the smallest nonnegative integer s such that there exist positive integers m and n with m n X X s = a = b . i j i =1 j =1
解析
- Random sequences a , a , . . . and b , b , . . . are chosen so that every element in each sequence is chosen 1 2 1 2 independently and uniformly from the set { 0 , 1 , 2 , 3 , . . . , 100 } . Compute the expected value of the smallest nonnegative integer s such that there exist positive integers m and n with m n X X s = a = b . i j i =1 j =1 Proposed by: Gabriel Wu Answer: 2550 Solution: Let’s first solve the problem, ignoring the possibility that the a and b can be zero. Call a i i P m positive integer s an A -sum if s = a for some nonnegative integer m (in particular, 0 is always i i =1 an A -sum). Define the term B -sum similarly. Let E be the expected value of the smallest positive integer that is both an A -sum and a B -sum. The first key observation to make is that if s is both an A -sum and a B -sum, then the distance to the next number that is both an A -sum and a B -sum is E . To see this, note that if m n X X s = a = b i i i =1 j =1 the distance to the next number that is both an A -sum and a B -sum is the minimal positive integer t ′ ′ so that there exist m and n so that ′ ′ m n X X t = a = b . m + i n + i i =1 j =1 This is the same question of which we defined E to be the answer, but with renamed variables, so the expected value of t is E . As a result, we conclude that the expected density of numbers that are both 1 A -sums and B -sums is . E 101 We now compute this density. Note that since the expected value of a is , the density of A -sums i 2 2 2 is . Also, the density of B -sums if . Moreover, as n goes to infinity, the probability that n is 101 101 2 2 an A -sum approaches and the probability that n is a B -sum approaches . Thus, the density of 101 101 2 4 101 numbers that are simultaneously A -sums and B -sums is , so E = . 2 101 4 We now add back the possibility that some of the a and b can be 0. The only way this changes our i i answer is that the s we seek can be 0, which happens if and only if a = b = 0. Thus our final answer 1 1 is 2 2 2 1 101 − 1 101 101 − 1 · 0 + · = = 2550 . 2 2 101 101 4 4