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"

(→‎Solution 2)
(→‎Solution)
Line 22: Line 22:
  
 
as desired.
 
as desired.
 +
 +
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>\displaystyle \{ 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 01:39, 6 June 2016

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

Slightly Clearer Solution

For any $k$, if there are $p_n(k)$ permutations that have $k$ fixed points, then we know that each fixed point is counted once in the product $k \cdot p_n{k}$. Therefore the given sum is simply the number of fixed points among all permutations of $\displaystyle \{ 1, \ldots , n \}$. However, if we take any $x$ such that $1 \le x \le n$ and $x$ is a fixed point, there are $(n-1)!$ ways to arrange the other numbers in the set. Therefore our desired sum becomes $n \cdot (n-1)! = n!$, so we are done.

Solution 2

The probability of any number $i$ where $1\le i\le n$ being a fixed point is $\frac{1}{n}$. Thus, the expected value of the number of fixed points is $n\times \frac{1}{n}=1$.

The expected value is also $\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}$.

Thus, \[\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1\] or \[\sum_{k=0}^{n} k \cdot p_n (k) = n!.\]

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=78795"