1989 IMO Problems/Problem 6

Problem:

A permutation $\{x_1, \ldots, x_{2n}\}$ of the set $\{1,2, \ldots, 2n\}$ where $\mbox{n}$ is a positive integer, is said to have property $T$ if $|x_i - x_{i + 1}| = n$ for at least one $i \in \{1,2, \ldots, 2n - 1\}$ . Show that, for each $\mbox{n}$ , there are more permutations with property $T$ than without.

So for the specific case when $n = 2$ .

We have the set $\{1,2,3,4\}$

To satisfy the condition, the 2 numbers must be adjacent and we can have either $(1,3), (3,1), (2,4), (4,2)$ where $(x,y)$ represents an adjacent pair.

To find those that satisfy $T$ we need to find: $(1,3) \cup (3,1) \cup (2,4) \cup (4,2)$

Using PIE we can find those that doesn't satisfy $T$ $\overline{(1,3) \cup (3,1) \cup (2,4) \cup (4,2)} = \overline{(1,3)} \cap \overline{(3,1)} \cap \overline{(2,4)} \cap \overline{(4,2)}$

Let $Q = |\overline{(1,3)} \cap \overline{(3,1)} \cap \overline{(2,4)} \cap \overline{(4,2)}|$

Defining an indicator function $I_y(x)$ where $y \in \{(1,3), (3,1), (2,4), (4,2)\}$ with domain $x \in \mathbb{U}$ such that $\mathbb{U}$ contains all sets $(x,y)$

$I_y(x) = \begin{cases} 0, & \mbox{if} \ \mbox{x} \ \notin \ \mbox{y} \\ 1, & \mbox{if} \ \mbox{x} \ \in \ \mbox{y} \end{cases}$

$Q = \sum_{x \in \mathbb{U}} I_{\overline{(1,3)}}(x) I_{\overline{(3,1)}}(x)I_{\overline{(2,4)}}(x)I_{\overline{(4,2)}}(x)$

$Q = \sum_{x \in \mathbb{U}} (1-I_{(1,3)}(x))(1-I_{(3,1)}(x))(1-I_{(2,4)}(x))(1-I_{(4,2)}(x))$

$Q = \sum_{x \in \mathbb{U}} 1 - \sum_{x \in \mathbb{U}}I_{(1,3)}(x)+I_{(3,1)}(x)+I_{(2,4)}(x)+I_{(4,2)}(x)+\sum_{x \in \mathbb{U}} I_{(1,3)}(x)I_{(3,1)}(x) + I_{(1,3)}(x)I_{(2,4)}(x)+I_{(1,3)}(x)I_{(4,2)}(x) + I_{(3,1)}(x)I_{(2,4)}(x) +I_{(3,1)}(x)I_{(4,2)}(x)+I_{(2,4)}(x)I_{(4,2)}(x)-\sum_{x \in \mathbb{U}}I_{(1,3)}(x)I_{(3,1)}(x)I_{(2,4)}(x)+I_{(1,3)}(x)I_{(2,4)}(x)I_{(4,2)}(x)+I_{(3,1)}(x)I_{(2,4)}(x)I_{(4,2)}(x)+I_{(1,3)}(x)I_{(3,1)}(x)I_{(4,2)}(x) + \sum_{x \in \mathbb{U}}I_{(1,3)}(x)I_{(3,1)}(x)I_{(2,4)}(x)I_{(4,2)}(x)$

Now to work out the cardinality of each consider the set $\{(1,3), (3,1)\}$ and $\{(2,4), (4,2)\}$

The first sum is obvious: $\sum_{x \in \mathbb{U}} 1 = 4!$

The second sum is also pretty obvious: $\sum_{x \in \mathbb{U}}I_{(1,3)}(x)+I_{(3,1)}(x)+I_{(2,4)}(x)+I_{(4,2)}(x) = 4!$

The third sum is not so obvious since we have terms that equal 0, eg, $I_{(1,3)}(x)I_{(3,1)}(x) = 0$ .

Thus we need to pick any 2 pairs from the 1st set and any 2 pairs from the 2nd set.

So there are $2 \times 2 = 4$ non-zero pairs. Each pair however has 2 ways to rearrange. So the third sum equals $2 \times 4 =8$

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 $\{1,2,3, \cdots, 2n\}$

Let $(1,1+n), (1+n,1), (2,2+n), (2+n,2), \cdots, (n,2n),(2n,n)$ represent the adjacent pairs. There are a total of 2n pairs.

To find those that satisfy T we need to find $(1,1+n) \cup (1+n,1) \cup (2,2+n) \cup (2+n,2) \cup \cdots \cup (n,2n) \cup (2n,n)$

Using PIE we can find the complement of T: $\overline{(1,1+n) \cup (1+n,1) \cup (2,2+n) \cup (2+n,2) \cup \cdots \cup (n,2n) \cup (2n,n)} = \overline{(1,1+n)} \cap \overline{(1+n,1)} \cap \overline{(2,2+n)} \cap \overline{(2+n,2)} \cap \cdots \cap \overline{(n,2n)} \cap \overline{(2n,n)}$

Let $Q_n = |\overline{(1,1+n)} \cap \overline{(1+n,1)} \cap \overline{(2,2+n)} \cap \overline{(2+n,2)} \cap \cdots \cap \overline{(n,2n)} \cap \overline{(2n,n)}|$

Now we define an indicator function $I_y(x)$ where $y \in \{(1,1+n), (1+n,1), (2,2+n), (2+n,2), \cdots, (n,2n),(2n,n)\}$

$I_y(x) = \begin{cases} 0, & \mbox{if} \ \mbox{x} \ \notin \ \mbox{y} \\ 1, & \mbox{if} \ \mbox{x} \ \in \ \mbox{y} \end{cases}$

$Q_n = \sum_{x \in \mathbb{U}} (1-I_{(1,1+n)}(x))(1-I_{(1+n,1)}(x))(1-I_{(2,2+n)}(x))(1-I_{(2+n,2)}(x)) \cdots (1-I_{(n,2n)}(x))(1-I_{(2n,n)}(x))$

$Q_n = \sum_{x \in \mathbb{U}} 1 - \sum_{x \in \mathbb{U}} I_{(1,1+n)}(x)+I_{(1+n,1)}(x)+ \cdots + I_{(n,2n)}(x) + I_{(2n,n)}(x) + \sum_{x \in \mathbb{U}} I_{(1,1+n)}(x)I_{(1+n,1)}(x)+I_{(1,1+n)}(x)I_{(2,2+n)}(x)+ \cdots + I_{(1+n,n)}(x)I_{(2n,n)}(x) \cdots - \sum_{x \in \mathbb{U}}I_{(1,1+n)}(x)I_{(1+n,1)}(x)I_{(2,2+n)}(x) \cdots+\sum_{x \in \mathbb{U}} (I_{(1,1+n)}(x))(I_{(1+n,1)}(x))(I_{(2,2+n)}(x))(I_{(2+n,2)}(x)) \cdots (I_{(n,2n)}(x))(I_{(2n,n)}(x))$

The first sum equals $(2n)!$

The second sum equals $\binom{2n}{1}(2n-1)!$

The third sum is a bit tricky since some pairs equal 0, thus consider all the different pairs placed into sets like this:

$\{(1,1+n), (1+n,1)\}, \{(2,2+n), (2+n,2)\}, \{(3,3+n), (3+n,n)\}, \cdots, \{(n,2n), (2n,n)\}$

We need 2 pairs, since there are $\mbox{n}$ sets, we need to pick 2 sets first $\implies \binom{n}{2}$ . But each set contains 2 terms, thus we can have $2^2$ different pairings for each 2 sets.

Therefore this sum equals $2^2\binom{n}{2}(2n-2)!$

The fourth sum is equal to $2^3\binom{n}{3}(2n-3)!$

The fifth sum is equal to $2^4\binom{n}{4}(2n-4)!$

. . .

The last sum is equal to $2^{2n}\binom{n}{2n}(2n-2n)!$

In total we have $Q_n = (2n)!-(2n)! + 2^2\binom{n}{2}(2n-2)! - 2^3\binom{n}{3}(2n-3)! + 2^4\binom{n}{4}(2n-4)! - \cdots + 2^{2n}\binom{n}{2n}(2n-2n)!$

$Q_n = \sum_{i=2}^{n}(-1)^{i}2^i\binom{n}{i}(2n-i)!$

So that means there are a total of $Q_n$ sets which does not satisfy $T$ .

Now we just have to prove that the number of sets that satisfy $T$ is larger than those that don't.

The number of sets that satisfies $T$ is equal to $(2n)!-Q_n$ .

So we need to prove $(2n)!-Q_n > Q_n$

$\implies (2n)! > 2Q_n$

First let $t_i$ represent $|(-1)^{i}2^i\binom{n}{i}(2n-i)!|$

$\therefore Q_n = t_2-t_3+t_4-t_5+ \cdots -t_{2n-1} + t_{2n}$

We see that $2t_2 = (-1)^{2}2^3\binom{n}{2}(2n-2)! = (2^2)\left(\frac{n!}{(n-2)!2!}\right)(2n-2)! = (2^3)\left(\frac{n(n-1)}{2}\right)(2n-2)! = 2n(2n-2)(2n-2)!$