HMMT 二月 2018 · 团队赛 · 第 7 题

HMMT February 2018 — Team Round — Problem 7

[ 50 ] Let [ n ] denote the set of integers { 1 , 2 , . . . , n } . We randomly choose a function f : [ n ] → [ n ], n out of the n possible functions. We also choose an integer a uniformly at random from [ n ]. Find b c k the probability that there exist positive integers b, c ≥ 1 such that f (1) = a and f ( a ) = 1. ( f ( x ) denotes the result of applying f to x k times).

解析

[ 50 ] Let [ n ] denote the set of integers { 1 , 2 , . . . , n } . We randomly choose a function f : [ n ] → [ n ], n out of the n possible functions. We also choose an integer a uniformly at random from [ n ]. Find b c k the probability that there exist positive integers b, c ≥ 1 such that f (1) = a and f ( a ) = 1. ( f ( x ) denotes the result of applying f to x k times). Proposed by: Allen Liu 1 Answer: n Given a function f , define N ( f ) to be the number of numbers that are in the same cycle as 1 (including 1 itself), if there is one, and zero if there is no such cycle. The problem is equivalent to finding E ( N ( f )) /n . Note that n − 1 n − 2 n − k + 1 1 P ( N ( f ) = k ) = · · · · · · · , n n n n n ∑ k and it suffices to compute P where P = P ( N ( f ) = k ). Observe that k k n k =1 ( ) n − 1 n − 2 3 2 1 n 1 P = · · · · · · · · · · n n n n n n n n ( ) n − 1 n − 2 3 2 n − 1 1 P = · · · · · · · · · n − 1 n n n n n n ( ) n − 1 n − 2 3 2 1 ⇒ P + P = · · · · · · · · n n − 1 n n n n n ( ) n − 1 n − 2 3 n − 2 1 P = · · · · · · · · n − 2 n n n n n ( ) n − 1 n − 2 3 1 ⇒ P + P + P = · · · · · · · n n − 1 n − 2 n n n n · · · n ∑ 1 ⇒ P = 1 · k n k =1 1 Therefore the answer is . n