Difference between revisions of "1987 IMO Problems/Problem 1"
(→Solution 2) |
(→Solution 2) |
||
| Line 30: | Line 30: | ||
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>. | ||
| − | |||
{{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]] | ||
Revision as of 12:22, 21 July 2012
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.
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, ![\[\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1\]](http://latex.artofproblemsolving.com/c/3/b/c3b7d1bac792f986ac46ed91b5bf43f8ced623d9.png)
or ![\[\sum_{k=0}^{n} k \cdot p_n (k) = n!\]](http://latex.artofproblemsolving.com/5/6/f/56f4fdb8c99f2ff910deb7d086d06730536d66f6.png)
.
| 1987 IMO (Problems) • Resources | ||
| Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
| All IMO Problems and Solutions | ||
