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

HMMT November 2015 — GEN Round — Problem 10

Let N be the number of functions f from { 1 , 2 , . . . , 101 } → { 1 , 2 , . . . , 101 } such that f (1) = 2 . Find the remainder when N is divided by 103 .

解析

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