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
Slightly Clearer Solution
For any , if there are permutations that have fixed points, then we know that each fixed point is counted once in the product . Therefore the given sum is simply the number of fixed points among all permutations of . However, if we take any such that and is a fixed point, there are ways to arrange the other numbers in the set. Therefore our desired sum becomes , so we are done.
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 .
Maybe try and find a formula for . It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose fixed points out of the total digits? Well, it can be done in ways. Now since we want exactly fixed points, what do we do with the remaining digits? Well we don't want any of those fixed. Clearly, of the spots left to put these points, we can put where it started off. So we have then spots to put one of the remaining points. Continuing on, we actually obtain a formula for , namely, . Now we have to be careful, because now, what about for ? We see that no matter how we choose fixed points, we always have to put the remain point into the last possible spot, which was the spot it started on. Therefore, we must eliminate the case .
is actually , where is the derangement counter function (See https://oeis.org/A000166)
|1987 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|