返回题库

HMMT 十一月 2017 · THM 赛 · 第 7 题

HMMT November 2017 — THM Round — Problem 7

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. O n a blackboard a stranger writes the values of s ( n ) for n = 0 , 1 , . . . , 7 − 1 , where s ( n ) denotes 7 7 the sum of digits of n in base 7. Compute the average value of all the numbers on the board.
解析
  1. O n a blackboard a stranger writes the values of s ( n ) for n = 0 , 1 , . . . , 7 − 1 , where s ( n ) denotes 7 7 the sum of digits of n in base 7. Compute the average value of all the numbers on the board. Proposed by: Ashwin Sah Answer: 3680 n 2 Solution 1: We solve for 0 to b − 1 and s ( n ) (i.e. base b ). b Let n = d . . . d in base b , where there may be leading zeros. Then s ( n ) = d + · · · + d , regardless 1 n b 1 n of the leading zeros. ∑ ∑ [ ] [ ] [ ] 2 2 2 E s ( n ) = E ( d + · · · + d ) = E d + 2 E [ d d ] , d 1 n i j i 1 ≤ i ≤ n 1 ≤ i<j ≤ n and now notice that we can treat choosing n uniformly as choosing the d uniformly independently i from { 0 , . . . , b − 1 } . Thus this simplifies to [ ] [ ] 2 2 2 E s ( n ) = n E d + n ( n − 1) E [ d ] . d 1 1 Now 2 2 [ ] 0 + · · · + ( b − 1) ( b − 1)(2 b − 1) 2 E d = = , 1 b 6 0 + · · · + ( b − 1) b − 1 E [ d ] = = , 1 b 2 so the answer is ( ) 2 ( b − 1)(2 b − 1) b − 1 n · + n ( n − 1) · . 6 2 Plugging in b = 7 , n = 20 yields the result. Solution 2: There are two theorems we will cite regarding variance and expected value. The first is that, for any variable X, 2 2 V ar ( X ) = E [ X ] − E [ X ] . The second is that, for two independent variables X and Y, V ar ( X + Y ) = V ar ( X ) + V ar ( Y ) . 2 Let X be the sum of all of the digits. We want to find E [ X ] . The expected of a single digit is 1 (0+1+2+3+4+5+6) = 3 . Thus, the expected value of the sum of the digits is E [ X ] = 20 × 3 = 60 , so 7 2 1 2 2 2 9+4+1+0+1+4+9 E [ X ] = 3600 . The variance of a single digit is [(0 − 3) +(1 − 3) + ... +(6 − 3) ] = = 4 . 7 7 Since the digits are independent, their variances add by the second theorem above. Therefore, the variance of the sum of all of the digits is V ar ( X ) = 20 × 4 = 80 . Finally, using the first theorem, we 2 2 have E [ X ] = E [ X ] + V ar ( X ) = 3680 .