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