Difference between revisions of "1987 IMO Problems/Problem 1"
(→Solution 2) |
(→Solution) |
||
Line 25: | Line 25: | ||
Slightly Clearer Solution | Slightly Clearer Solution | ||
− | For any <math>k</math>, if there are <math>p_n(k)</math> permutations that have <math>k</math> fixed points, then we know that each fixed point is counted once in the product <math>k \cdot p_n{k}</math>. Therefore the given sum is simply the number of fixed points among all permutations of <math> | + | For any <math>k</math>, if there are <math>p_n(k)</math> permutations that have <math>k</math> fixed points, then we know that each fixed point is counted once in the product <math>k \cdot p_n{k}</math>. Therefore the given sum is simply the number of fixed points among all permutations of <math>\{ 1, \ldots , n \}</math>. However, if we take any <math>x</math> such that <math>1 \le x \le n</math> and <math>x</math> is a fixed point, there are <math>(n-1)!</math> ways to arrange the other numbers in the set. Therefore our desired sum becomes <math>n \cdot (n-1)! = n!</math>, so we are done. |
==Solution 2== | ==Solution 2== |
Revision as of 16:00, 23 August 2021
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
1987 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |