Difference between revisions of "1987 IMO Problems/Problem 1"
(→Solution 2) |
|||
(3 intermediate revisions by one other user not shown) | |||
Line 35: | Line 35: | ||
== Note == | == Note == | ||
− | Maybe try and find a formula for <math>p_n(k)</math>. It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose <math>k</math> fixed points out of the <math>n</math> total digits? Well, it can be done in <math>\binom{n}{k}</math> ways. Now since we want exactly <math> | + | Maybe try and find a formula for <math>p_n(k)</math>. It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose <math>k</math> fixed points out of the <math>n</math> total digits? Well, it can be done in <math>\binom{n}{k}</math> ways. Now since we want exactly <math>k</math> fixed points, what do we do with the remaining <math>(n-k)</math> digits? Well we don't want any of those fixed. Clearly, of the <math>(n-k)</math> spots left to put these <math>(n-k)</math> points, we can put where it started off. So we have then <math>(n-k-1)</math> spots to put one of the remaining <math>(n-k)</math> points. Continuing on, we actually obtain a formula for <math>p_n(k)</math>, namely, <math>\binom{n}{k}(n-k-1)(n-k-2)\dots1</math>. Now we have to be careful, because now, what about for <math>k=n-1</math>? We see that no matter how we choose <math>n-1</math> fixed points, we always have to put the remain point into the last possible spot, which was the spot it started on. Therefore, we must eliminate the case <math>k=n-1</math>. |
+ | |||
+ | ~th1nq3r | ||
+ | |||
+ | == Note 2 == | ||
+ | <math>p_n(k)</math> is actually <math>\binom{n}{k}d(n-k)</math>, where <math>d</math> is the derangement counter function (See https://oeis.org/A000166) | ||
{{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]] |
Latest revision as of 18:54, 10 May 2023
Contents
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.
Slightly Clearer Solution
For any , if there are
permutations that have
fixed points, then we know that each fixed point is counted once in the product
. Therefore the given sum is simply the number of fixed points among all permutations of
. However, if we take any
such that
and
is a fixed point, there are
ways to arrange the other numbers in the set. Therefore our desired sum becomes
, so we are done.
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, or
Note
Maybe try and find a formula for . It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose
fixed points out of the
total digits? Well, it can be done in
ways. Now since we want exactly
fixed points, what do we do with the remaining
digits? Well we don't want any of those fixed. Clearly, of the
spots left to put these
points, we can put where it started off. So we have then
spots to put one of the remaining
points. Continuing on, we actually obtain a formula for
, namely,
. Now we have to be careful, because now, what about for
? We see that no matter how we choose
fixed points, we always have to put the remain point into the last possible spot, which was the spot it started on. Therefore, we must eliminate the case
.
~th1nq3r
Note 2
is actually
, where
is the derangement counter function (See https://oeis.org/A000166)
1987 IMO (Problems) • Resources | ||
Preceded by First question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |