HMMT 十一月 2017 · THM 赛 · 第 7 题
HMMT November 2017 — THM Round — Problem 7
题目详情
英文原题
- 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.
解析
英文解析
- 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 ).
Let n = d . . . d in base b , where there may be leading zeros. Then s ( n ) = d + · · · + d , regardlessb
1 n b 1 nof the leading zeros.
∑ ∑
[ ] [ ] [ ]
2 2 2
E s ( n ) = E ( d + · · · + d ) = E d + 2 E [ d d ] ,
d 1 n i ji
1 ≤ i ≤ n 1 ≤ i<j ≤ nand now notice that we can treat choosing n uniformly as choosing the d uniformly independentlyfrom { 0 , . . . , b − 1 } . Thus this simplifies toi
[ ] [ ]
2 22
E s ( n ) = n E d + n ( n − 1) E [ d ] .
d 1
Now 1
2 2
[ ]
0 + · · · + ( b − 1) ( b − 1)(2 b − 1)
E d = = ,2
b 61
0 + · · · + ( b − 1) b − 1
E [ d ] = = ,
b 21
so the answer is
( )
( b − 1)(2 b − 1) b − 12
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 isthat, 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 ) .
Let X be the sum of all of the digits. We want to find E [ X ] . The expected of a single digit is 2
(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 1
2 1 2 2 2 9+4+1+0+1+4+97
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, thevariance 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 .