1987 IMO Problems/Problem 1
Contents
Problem
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
.)
Solution
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
,
as desired.
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.
Solution 2
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
Note
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
.
~th1nq3r
Note 2
is actually
, where
is the derangement counter function (See https://oeis.org/A000166)
1987 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |