Difference between revisions of "1989 IMO Problems/Problem 6"
(→Added a new solution.) |
(→Solution 2) |
||
Line 134: | Line 134: | ||
<cmath>|F| = \bigg|\bigcup_{i=1}^n F_i \bigg| = \sum_{i=1}^{2n-1} |F_i| - \sum_{1\leq i<j \leq 2n-1} |F_i \cap F_j| + E, \tag{1}</cmath> | <cmath>|F| = \bigg|\bigcup_{i=1}^n F_i \bigg| = \sum_{i=1}^{2n-1} |F_i| - \sum_{1\leq i<j \leq 2n-1} |F_i \cap F_j| + E, \tag{1}</cmath> | ||
− | for some <math>E | + | for some <math>E \geq 0</math>. Let’s calculate the first two sums on the right-hand side. |
For any <math>i</math>, <math>|F_i| = 2n \cdot (2n - 2)!</math>, since there are are <math>2n</math> choices for <math>x_i</math>, which fixes <math>x_{i+1}</math>, and <math>(2n-2)!</math> choices for the remaining elements. Thus | For any <math>i</math>, <math>|F_i| = 2n \cdot (2n - 2)!</math>, since there are are <math>2n</math> choices for <math>x_i</math>, which fixes <math>x_{i+1}</math>, and <math>(2n-2)!</math> choices for the remaining elements. Thus | ||
Line 153: | Line 153: | ||
Let’s plug this into <math>(1)</math>: | Let’s plug this into <math>(1)</math>: | ||
− | <cmath>|F| = \sum_{i=1}^{2n - 1} |F_i| - \sum_{1\leq i < j \leq 2n-1} |F_i \cap F_j| + E > (2n)! - \frac{(2n)!}{2} + E | + | <cmath>|F| = \sum_{i=1}^{2n - 1} |F_i| - \sum_{1\leq i < j \leq 2n-1} |F_i \cap F_j| + E > (2n)! - \frac{(2n)!}{2} + E \geq \frac{(2n)!}{2}.</cmath> |
So more than half of the <math>(2n)!</math> permutations of <math>\{1, \ldots, 2n\}</math> have property <math>T</math>. | So more than half of the <math>(2n)!</math> permutations of <math>\{1, \ldots, 2n\}</math> have property <math>T</math>. |
Revision as of 08:40, 2 May 2023
Contents
Problem
A permutation of the set
where
is a positive integer, is said to have property
if
for at least one
. Show that, for each
, there are more permutations with property
than without.
Solution 1
So for the specific case when .
We have the set
To satisfy the condition, the 2 numbers must be adjacent and we can have either where
represents an adjacent pair.
To find those that satisfy we need to find:
Using PIE we can find those that doesn't satisfy
Let
Defining an indicator function where
with domain
such that
contains all sets
Now to work out the cardinality of each consider the set and
The first sum is obvious:
The second sum is also pretty obvious:
The third sum is not so obvious since we have terms that equal 0, eg, .
Thus we need to pick any 2 pairs from the 1st set and any 2 pairs from the 2nd set.
So there are non-zero pairs. Each pair however has 2 ways to rearrange. So the third sum equals
The fourth sum is 0 since we need 3 sets but we only have 2 to pick from.
The fifth sum is also 0 by the same argument as above.
Now we can generalise.
Consider the set
Let represent the adjacent pairs. There are a total of 2n pairs.
To find those that satisfy T we need to find
Using PIE we can find the complement of T:
Let
Now we define an indicator function where
The first sum equals
The second sum equals
The third sum is a bit tricky since some pairs equal 0, thus consider all the different pairs placed into sets like this:
We need 2 pairs, since there are sets, we need to pick 2 sets first
. But each set contains 2 terms, thus we can have
different pairings for each 2 sets.
Therefore this sum equals
The fourth sum is equal to
The fifth sum is equal to
. . .
The last sum is equal to
In total we have
So that means there are a total of sets which does not satisfy
.
Now we just have to prove that the number of sets that satisfy is larger than those that don't.
The number of sets that satisfies is equal to
.
So we need to prove
First let represent
We see that
But
Next take and
for example.
means at least 3 pairs satisfy T and
means at least 4 pairs satisfy
.
But at least 4 pairs is a subset of at least 3 pairs which means
Generalising this leads to
So
Solution 2
Let be the number of permutations with property
, and
be the set of permutations
such that
. By the inclusion-exclusion principle,
for some . Let’s calculate the first two sums on the right-hand side.
For any ,
, since there are are
choices for
, which fixes
, and
choices for the remaining elements. Thus
Now let’s compute , where
. It’s not possible that
, since that would imply
. So
if
. If
, then
(there are
choices for
,
for
, and
for everything else.)
How often is ? We know
is at least
and at most
, and for any value of
, there are
possible values for
. So the number of non-empty intersections
is
Now we can compute
Let’s plug this into :
So more than half of the permutations of
have property
.
See Also
1989 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |