1987 IMO Problems/Problem 1
Let be the number of permutations of the set , which have exactly fixed points. Prove that
(Remark: A permutation of a set is a one-to-one mapping of onto itself. An element in is called a fixed point of the permutation if .)
The sum in question simply counts the total number of fixed points in all permutations of the set. But for any element of the set, there are permutations which have as a fixed point. Therefore
The probability of any number where being a fixed point is . Thus, the expected value of the number of fixed points is .
The expected value is also .
Thus, , or . Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|1987 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|