1989 IMO Problems/Problem 6
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.
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
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:
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
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
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 .
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 .
|1989 IMO (Problems) • Resources
|1 • 2 • 3 • 4 • 5 • 6
|All IMO Problems and Solutions