During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

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

Line 23: Line 23:
 
as desired.
 
as desired.
  
 +
==Solution 2==
  
 +
The probability of any number <math>i</math> where <math>1\le i\le n</math> being a fixed point is <math>\frac{1}{n}</math>. Thus, the expected value of the number of fixed points is <math>n\times \frac{1}{n}=1</math>.
  
 +
The expected value is also <math>\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}</math>.
  
 +
Thus, <cmath>\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1</cmath>, or \[\sum_{k=0}^{n} k \cdot p_n (k) = n!]\.
 
{{alternate solutions}}
 
{{alternate solutions}}
  

Revision as of 12:21, 21 July 2012

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.

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!]\. 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
Invalid username
Login to AoPS