HMMT 二月 2015 · 冲刺赛 · 第 27 题

英文解析

27. [ 17 ] Let a, b be integers chosen independently and uniformly at random from the set { 0 , 1 , 2 , . . . , 80 } .
    ( )
    a !a
    Compute the expected value of the remainder when the binomial coefficient = is dividedb b !( a − b )!
    ( ) ( )
    0 aby 3. (Here = 1 and = 0 whenever a < b .)
    0 b
    1816
    Answer: By Lucas’ Theorem we’re looking at
    6561
    ( )
    ∏4
    ibiai =1
    Gutswhere the a and b are the digits of a and b in base 3. If any a < b , then the product is zero moduloi i i i

( ) ( ) ( ) ( ) ( ) ( )
2 2 2 1 1 0
Otherwise, the potential residues are = 1, = 2, = 1, = 1, = 1, = 1.
0 1 2 0 1 0
So each term in the product has a chance of being zero; given that everything is nonzero, each term 1
1 53
has a chance of being 2 and a chance of being 1. The probability that an even number of terms
6 6
are 1 given that none are zero is then given by the roots of unity filter
5 1 5 1
4 4
( + · (1)) + ( + · ( − 1))
81 + 16 97
6 6 6 6 = = .
2 162 162
Thus the expected value is
( ) ( )
2 97 18164
2 − = .
3 162 6561