返回题库

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

HMMT November 2017 — THM Round — Problem 7

专题
Contest 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 ).
    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 .