1987 IMO Problems/Problem 1

Revision as of 12:59, 3 December 2021 by Th1nq3r (talk | contribs) (Note)

Problem

Let $p_n (k)$ be the number of permutations of the set $\{ 1, \ldots , n \} , \; n \ge 1$, which have exactly $k$ fixed points. Prove that

$\sum_{k=0}^{n} k \cdot p_n (k) = n!$.

(Remark: A permutation $f$ of a set $S$ is a one-to-one mapping of $S$ onto itself. An element $i$ in $S$ is called a fixed point of the permutation $f$ if $f(i) = i$.)

Solution

The sum in question simply counts the total number of fixed points in all permutations of the set. But for any element $i$ of the set, there are $(n-1)!$ permutations which have $i$ as a fixed point. Therefore

$\sum_{k=0}^{n} k \cdot p_n (k) = n!$,

as desired.

Slightly Clearer Solution

For any $k$, if there are $p_n(k)$ permutations that have $k$ fixed points, then we know that each fixed point is counted once in the product $k \cdot p_n{k}$. Therefore the given sum is simply the number of fixed points among all permutations of $\{ 1, \ldots , n \}$. However, if we take any $x$ such that $1 \le x \le n$ and $x$ is a fixed point, there are $(n-1)!$ ways to arrange the other numbers in the set. Therefore our desired sum becomes $n \cdot (n-1)! = n!$, so we are done.

Solution 2

The probability of any number $i$ where $1\le i\le n$ being a fixed point is $\frac{1}{n}$. Thus, the expected value of the number of fixed points is $n\times \frac{1}{n}=1$.

The expected value is also $\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}$.

Thus, \[\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1\] or \[\sum_{k=0}^{n} k \cdot p_n (k) = n!.\]

Note

Maybe try and find a formula for $p_n(k)$. It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose $k$ fixed points out of the $n$ total digits? Well, it can be done in $\binom{n}{k}$ ways. Now since we want exactly $k$ fixed points, what do we do with the remaining $(n-k)$ digits? Well we don't want any of those fixed. Clearly, of the $(n-k)$ spots left to put these $(n-k)$ points, we can put where it started off. So we have then $(n-k-1)$ spots to put one of the remaining $(n-k)$ points. Continuing on, we actually obtain a formula for $p_n(k)$, namely, $\binom{n}{k}(n-k-1)(n-k-2)\dots1$. Now we have to be careful, because now, what about for $k=n-1$? We see that no matter how we choose $n-1$ 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 $k=n-1$. ~th1nq3r

1987 IMO (Problems) • Resources
Preceded by
First question
1 2 3 4 5 6 Followed by
Problem 2
All IMO Problems and Solutions