Difference between revisions of "1989 IMO Problems/Problem 6"
(→Added a new solution.) |
Bennetthuang (talk | contribs) (→Solution 3) |
||
(6 intermediate revisions by 2 users not shown) | |||
Line 132: | Line 132: | ||
Let <math>F</math> be the number of permutations with property <math>T</math>, and <math>F_i</math> be the set of permutations <math>\{ x_1, x_2, \ldots, x_{2n} \}</math> such that <math>|x_i - x_{i+1}| = n</math>. By the inclusion-exclusion principle, | Let <math>F</math> be the number of permutations with property <math>T</math>, and <math>F_i</math> be the set of permutations <math>\{ x_1, x_2, \ldots, x_{2n} \}</math> such that <math>|x_i - x_{i+1}| = n</math>. By the inclusion-exclusion principle, | ||
− | <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 | + | <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 far right. |
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 140: | Line 140: | ||
<cmath> \sum_{i=1}^{2n - 1}|F_i| = 2n \cdot (2n - 2)! \cdot (2n - 1) = (2n)! </cmath> | <cmath> \sum_{i=1}^{2n - 1}|F_i| = 2n \cdot (2n - 2)! \cdot (2n - 1) = (2n)! </cmath> | ||
− | Now let’s compute <math>|F_i \cap F_j|</math>, where <math>1 \leq i < j \leq 2n</math>. It’s not possible that <math>|x_i - x_{i+1}| = |x_{i+1}- x_{i+2}| = n</math>, since that would imply <math>x_i = x_{i+2}</math>. So <math>|F_i \cap F_j| = 0</math> if <math>j = i + 1</math>. If <math>j > i + 1</math>, then <math>|F_i \cap F_j| = 2n \cdot (2n - 2) \cdot (2n - 4)!</math> (there are <math>2n</math> choices for <math>x_i, x_{i+1}</math>, <math>2n - 2</math> for <math>x_j, x_{j+1}</math>, and <math>(2n - 4)!</math> for everything else.) | + | Now let’s compute <math>|F_i \cap F_j|</math>, where <math>1 \leq i < j \leq 2n - 1</math>. It’s not possible that <math>|x_i - x_{i+1}| = |x_{i+1}- x_{i+2}| = n</math>, since that would imply <math>x_i = x_{i+2}</math>. So <math>|F_i \cap F_j| = 0</math> if <math>j = i + 1</math>. If <math>j > i + 1</math>, then <math>|F_i \cap F_j| = 2n \cdot (2n - 2) \cdot (2n - 4)!</math> (there are <math>2n</math> choices for <math>x_i, x_{i+1}</math>, <math>2n - 2</math> for <math>x_j, x_{j+1}</math>, and <math>(2n - 4)!</math> for everything else.) |
How often is <math>|F_i \cap F_j| \neq 0</math>? We know <math>i</math> is at least <math>1</math> and at most <math>2n - 3</math>, and for any value of <math>i</math>, there are <math>2n - 2 - i</math> possible values for <math>j</math>. So the number of non-empty intersections <math>|F_i \cap F_j|</math> is | How often is <math>|F_i \cap F_j| \neq 0</math>? We know <math>i</math> is at least <math>1</math> and at most <math>2n - 3</math>, and for any value of <math>i</math>, there are <math>2n - 2 - i</math> possible values for <math>j</math>. So the number of non-empty intersections <math>|F_i \cap F_j|</math> is | ||
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>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | Let <math>A_n</math> be the set of permutations of <math>1,2, \ldots,2n</math> not having property <math>T</math> and let <math>B_n</math> be the set of permutations of <math>1,2, \ldots,2n</math> having exactly one value of <math>k\geq2</math> such that <math>|x_k-x_{k+1}|=n</math>. We will prove a 1-1 correspondence between <math>A_n</math> and <math>B_n</math>. | ||
+ | |||
+ | |||
+ | Consider any permutation in <math>A_n</math>. Now take <math>x_1</math> and for the unique value <math>k</math> such that <math>|x_1-x_k|=n</math>, put <math>x_1</math> in the spot right before <math>x_k</math>. This will give us a permutation that belongs in the set <math>B_n</math>. Now consider a permutation in <math>B_n</math>. If you take <math>x_k</math> and put it as the first term, you'll get a permutation that belongs in set <math>A_n</math>.Therefore, we've proved a 1-1 correspondence between the two. | ||
+ | |||
+ | |||
+ | Because <math>|A_n|</math> is clearly less than the number of permutations with property <math>T</math>, we finally have that the number of permutations with property <math>T</math> is greater than the number of permutations without <math>T</math>. | ||
+ | |||
+ | |||
+ | ~BennettHuang | ||
== See Also == {{IMO box|year=1989|num-b=5|after=Last Question}} | == See Also == {{IMO box|year=1989|num-b=5|after=Last Question}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 12:26, 26 July 2023
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 far right.
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
.
Solution 3
Let be the set of permutations of
not having property
and let
be the set of permutations of
having exactly one value of
such that
. We will prove a 1-1 correspondence between
and
.
Consider any permutation in . Now take
and for the unique value
such that
, put
in the spot right before
. This will give us a permutation that belongs in the set
. Now consider a permutation in
. If you take
and put it as the first term, you'll get a permutation that belongs in set
.Therefore, we've proved a 1-1 correspondence between the two.
Because is clearly less than the number of permutations with property
, we finally have that the number of permutations with property
is greater than the number of permutations without
.
~BennettHuang
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 |