HMMT 十一月 2016 · GEN 赛 · 第 8 题

英文解析

8. Let S = { 1 , 2 , . . . 2016 } , and let f be a randomly chosen bijection from S to itself. Let n be the smallest
   ( n ) ( i ) ( i − 1)
   positive integer such that f (1) = 1, where f ( x ) = f ( f ( x )). What is the expected value of n ?
   Proposed by: Eshaan Nichani
   2017
   Answer:
   2 ( k − 1)2
   Say that n = k . Then 1, f (1) , f (1) , . . . , f (1) are all distinct, which means there are 2015 ·
   2014 · · · (2016 − k + 1) ways to assign these values. There is 1 possible value of f (1), and (2016 − k )!kways to assign the image of the 2016 − k remaining values. Thus the probability that n = k is .1
   2016
   1 2017
   Therefore the expected value of n is (1 + 2 + · · · + 2016) =
   2016 2
   ia