HMMT 十一月 2015 · GEN 赛 · 第 10 题

英文解析

10. Let N be the number of functions f from { 1 , 2 , . . . , 101 } → { 1 , 2 , . . . , 101 } such that f (1) = 2 . Findthe remainder when N is divided by 103 .
    Proposed by: Yang Liu
    Answer: 43
    For convenience, let n = 101 . Compute the number of functions such that f (1) = 1 . Since n is ann − 1
    prime, there are 2 cases: the order of 1 is either 1 or n . The first case gives n functions, and thensecond case gives ( n − 1)! functions. By symmetry, the number of ways for f (1) = 2 isn n − 1 n − 11
    · ( n − n − ( n − 1)!) = n − ( n − 2)! .
    n − 1
    Plugging in n = 101 , we need to find
    101!
    100 − 2
    101 − 99! ≡ ( − 2) −
    = 1 / 4 − 1 / 6 = 1 / 12 = 43 (mod 103) .6