A random function

Level pending

Let S = { 1 , 2 , ⋯ , 2014 } \mathbb{S}= \{1, 2, \cdots , 2014\} . A bijective function f : S → S f:\mathbb{S} \rightarrow \mathbb{S} is randomly chosen. Find the expected number of integers n n ( 1 ≤ n ≤ 2014 ) \left ( 1 \leq n \leq 2014 \right ) such that f ( n ) = n f(n)=n .

Note: This problem isn't original. I got this problem from an INMO training camp.


The answer is 1.

Sreejato Bhattacharya by Sreejato Bhattacharya , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Michael Tang
Jan 5, 2014

For each n , n, the probability that f ( n ) = n f(n) = n is 1 2014 , \dfrac{1}{2014}, since f ( n ) f(n) is chosen from the set { 1 , 2 , … , 2014 } , \{1, 2, \ldots, 2014\}, with each value being equally likely. Since there are 2014 2014 values of n , n, by linearity of expectation, there is 2014 ⋅ 1 2014 = 1 2014 \cdot \dfrac{1}{2014} = \boxed{1} expected value of n n such that f ( n ) = n . f(n) = n.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

A way to rephrase the result: taking a permutation of a set is expected to result in exactly one fixed point.

Michael Tang - 7 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...