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 divided b b !( a − b )! ( ) ( ) 0 a by 3. (Here = 1 and = 0 whenever a < b .) 0 b 1816 Answer: By Lucas’ Theorem we’re looking at 6561 ( ) 4 ∏ a i b i i =1 Guts where the a and b are the digits of a and b in base 3. If any a < b , then the product is zero modulo i 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 1 So each term in the product has a chance of being zero; given that everything is nonzero, each term 3 1 5 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 ( ) ( ) 4 2 97 1816 2 − = . 3 162 6561