Difference between revisions of "1987 IMO Problems/Problem 1"
(→Solution 2) |
(→Note) |
||
(4 intermediate revisions by the same user not shown) | |||
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== | ||
Line 33: | Line 33: | ||
Thus, <cmath>\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1</cmath> or <cmath>\sum_{k=0}^{n} k \cdot p_n (k) = n!.</cmath> | Thus, <cmath>\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1</cmath> or <cmath>\sum_{k=0}^{n} k \cdot p_n (k) = n!.</cmath> | ||
+ | |||
+ | == Note == | ||
+ | Maybe try and find a formula for <math>p_n(k)</math>. It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose <math>k</math> fixed points out of the <math>n</math> total digits? Well, it can be done in <math>\binom{n}{k}</math> ways. Now since we want exactly <math>k</math> fixed points, what do we do with the remaining <math>(n-k)</math> digits? Well we don't want any of those fixed. Clearly, of the <math>(n-k)</math> spots left to put these <math>(n-k)</math> points, we can put where it started off. So we have then <math>(n-k-1)</math> spots to put one of the remaining <math>(n-k)</math> points. Continuing on, we actually obtain a formula for <math>p_n(k)</math>, namely, <math>\binom{n}{k}(n-k-1)(n-k-2)\dots1</math>. Now we have to be careful, because now, what about for <math>k=n-1</math>? We see that no matter how we choose <math>n-1</math> 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 <math>k=n-1</math>. | ||
+ | |||
+ | ~th1nq3r | ||
{{IMO box|before=First question|num-a=2|year=1987}} | {{IMO box|before=First question|num-a=2|year=1987}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 12:59, 3 December 2021
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
1987 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |