Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1987 IMO Problems/Problem 1"

m (→‎Resources)
(creation)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math> \displaystyle p_n (k) </math> be the number of permutations of the set <math> \displaystyle \{ 1, \ldots , n \} , \; n \ge 1 </math>, which have exactly <math> \displaystyle k </math> fixed points.  Prove that
+
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> \displaystyle f </math> of a set <math> \displaystyle S </math> is a one-to-one mapping of <math> \displaystyle S </math> onto itself.  An element <math> \displaystyle i </math> in <math> \displaystyle S </math> is called a fixed point of the permutation <math> \displaystyle f </math> if <math> \displaystyle f(i) = i </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> \displaystyle i </math> of the set, there are <math> \displaystyle (n-1)! </math> permutations which have <math> \displaystyle i </math> as a fixed point.  Therefore
+
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}}
−
== Resources ==
 
−
 
 
−
* [[1987 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366512#p366512 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 19:48, 25 October 2007

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 questions 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.


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1987_IMO_Problems/Problem_1&oldid=18779"