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 ],
out of the n possible functions. We also choose an integer a uniformly at random from [ n ]. Findnb c kthe 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 ],
out of the n possible functions. We also choose an integer a uniformly at random from [ n ]. Findnb c kthe 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
Answer:1
Given a function f , define N ( f ) to be the number of numbers that are in the same cycle as 1 (including 1 nitself), if there is one, and zero if there is no such cycle. The problem is equivalent to finding E ( N ( f )) /n .
Note thatn − 1 n − 2 n − k + 1 1
P ( N ( f ) = k ) = · · · · · · · ,
n n n nn
∑
and it suffices to compute P where P = P ( N ( f ) = k ). Observe thatkk kk =1 n
( )
n − 1 n − 2 3 2 1 n 1
P = · · · · · · · · · ·
n n n n n n nn
( )
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
⇒ P = 1 ·1
k =1 nk
Therefore the answer is .1 n