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

HMMT November 2016 — GEN Round — Problem 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 ? a i

解析

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 2 ( k − 1) Say that n = k . Then 1, f (1) , f (1) , . . . , f (1) are all distinct, which means there are 2015 · k 2014 · · · (2016 − k + 1) ways to assign these values. There is 1 possible value of f (1), and (2016 − k )! 1 ways to assign the image of the 2016 − k remaining values. Thus the probability that n = k is . 2016 1 2017 Therefore the expected value of n is (1 + 2 + · · · + 2016) = 2016 2 a i