Difference between revisions of "1987 IMO Problems/Problem 1"
m (→Resources) |
(creation) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | Let <math> | + | Let <math>p_n (k) </math> be the number of permutations of the set <math>\{ 1, \ldots , n \} , \; n \ge 1 </math>, which have exactly <math>k </math> fixed points. Prove that |
<center> | <center> | ||
Line 9: | Line 9: | ||
</center> | </center> | ||
− | (Remark: A permutation <math> | + | (Remark: A permutation <math>f </math> of a set <math>S </math> is a one-to-one mapping of <math>S </math> onto itself. An element <math>i </math> in <math>S </math> is called a fixed point of the permutation <math>f </math> if <math>f(i) = i </math>.) |
== Solution == | == Solution == | ||
− | The sum in questions simply counts the total number of fixed points in all permutations of the set. But for any element <math> | + | The sum in questions simply counts the total number of fixed points in all permutations of the set. But for any element <math>i </math> of the set, there are <math>(n-1)! </math> permutations which have <math>i </math> as a fixed point. Therefore |
<center> | <center> | ||
Line 26: | Line 26: | ||
{{alternate solutions}} | {{alternate solutions}} | ||
− | + | {{IMO box|before=First question|num-a=2|year=1987}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Revision as of 19:48, 25 October 2007
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 questions 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.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
1987 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |