# 1989 IMO Problems/Problem 6

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.

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