Difference between revisions of "1989 IMO Problems/Problem 6"

Latest revision as of 11:26, 26 July 2023

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.

Solution 1

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)!$

But $(2n)! = (2n)(2n-1)(2n-2)!$

$(2n)(2n-1)(2n-2)! > 2n(2n-2)(2n-2)!$

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

Next take $t_3$ and $t_4$ for example.

$t_3$ means at least 3 pairs satisfy T and $t_4$ means at least 4 pairs satisfy $T$ .

But at least 4 pairs is a subset of at least 3 pairs which means $t_4 \subset t_3 \implies |t_3| \ge |t_4|$

Generalising this leads to $t_i \ge t_{i+1}$

So $2Q_n = 2t_2 + 2(t_4-t_3) + \cdots 2(t_{2n} - t_{2n-1})$

$\{(t_4-t_3), \cdots, (t_{2n}-t_{2n-1})\} \le 0$

$\implies 2t_2 + 2(t_4-t_3) + \cdots 2(t_{2n} - t_{2n-1}) \le 2t_2 < (2n)!$

$\therefore 2Q_n < (2n)!$

$\mbox{Q.E.D}$

Solution 2

Let $F$ be the number of permutations with property $T$ , and $F_i$ be the set of permutations $\{ x_1, x_2, \ldots, x_{2n} \}$ such that $|x_i - x_{i+1}| = n$ . By the inclusion-exclusion principle,

$|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}$

for some $E \geq 0$ . Let’s calculate the first two sums on the far right.

For any $i$ , $|F_i| = 2n \cdot (2n - 2)!$ , since there are are $2n$ choices for $x_i$ , which fixes $x_{i+1}$ , and $(2n-2)!$ choices for the remaining elements. Thus

$\sum_{i=1}^{2n - 1}|F_i| = 2n \cdot (2n - 2)! \cdot (2n - 1) = (2n)!$

Now let’s compute $|F_i \cap F_j|$ , where $1 \leq i < j \leq 2n - 1$ . It’s not possible that $|x_i - x_{i+1}| = |x_{i+1}- x_{i+2}| = n$ , since that would imply $x_i = x_{i+2}$ . So $|F_i \cap F_j| = 0$ if $j = i + 1$ . If $j > i + 1$ , then $|F_i \cap F_j| = 2n \cdot (2n - 2) \cdot (2n - 4)!$ (there are $2n$ choices for $x_i, x_{i+1}$ , $2n - 2$ for $x_j, x_{j+1}$ , and $(2n - 4)!$ for everything else.)

How often is $|F_i \cap F_j| \neq 0$ ? We know $i$ is at least $1$ and at most $2n - 3$ , and for any value of $i$ , there are $2n - 2 - i$ possible values for $j$ . So the number of non-empty intersections $|F_i \cap F_j|$ is $\sum_{i=1}^{2n-3} 2n - 2 - i = \sum_{i=1}^{2n-3}i = \frac{(2n-3)(2n-2)}{2}.$ Now we can compute $\begin{align*} \sum_{1\leq i < j \leq 2n-1} |F_i \cap F_j| &= 2n \cdot (2n - 2) \cdot (2n - 4)! \cdot \frac{(2n - 3)(2n - 2)}{2} \\ &= \frac{2n \cdot (2n-2)^2 \cdot (2n - 3)!}{2} = \frac{(2n)!}{2} \cdot \frac{2n - 2}{2n - 1} \\ &< \frac{(2n)!}{2}. \end{align*}$

Let’s plug this into $(1)$ :

$|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}.$

So more than half of the $(2n)!$ permutations of $\{1, \ldots, 2n\}$ have property $T$ .

Solution 3

Let $A_n$ be the set of permutations of $1,2, \ldots,2n$ not having property $T$ and let $B_n$ be the set of permutations of $1,2, \ldots,2n$ having exactly one value of $k\geq2$ such that $|x_k-x_{k+1}|=n$ . We will prove a 1-1 correspondence between $A_n$ and $B_n$ .

Consider any permutation in $A_n$ . Now take $x_1$ and for the unique value $k$ such that $|x_1-x_k|=n$ , put $x_1$ in the spot right before $x_k$ . This will give us a permutation that belongs in the set $B_n$ . Now consider a permutation in $B_n$ . If you take $x_k$ and put it as the first term, you'll get a permutation that belongs in set $A_n$ .Therefore, we've proved a 1-1 correspondence between the two.

Because $|A_n|$ is clearly less than the number of permutations with property $T$ , we finally have that the number of permutations with property $T$ is greater than the number of permutations without $T$ .

~BennettHuang

@@ Line 3: / Line 3: @@
 A permutation <math>\{x_1, \ldots, x_{2n}\}</math> of the set<math> \{1,2, \ldots, 2n\}</math> where <math>\mbox{n}</math> is a positive integer, is said to have property <math>T</math> if <math>|x_i - x_{i + 1}| = n</math> for at least one <math>i \in \{1,2, \ldots, 2n - 1\}</math>. Show that, for each <math>\mbox{n}</math>, there are more permutations with property <math>T</math> than without.
-==Solution==
+==Solution 1==
 So for the specific case when <math>n = 2</math>.
@@ Line 127: / Line 127: @@
 <math>\mbox{Q.E.D}</math>
+==Solution 2==
+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 \tag{1}</cmath>
+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
+<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 - 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
+<cmath>\sum_{i=1}^{2n-3} 2n - 2 - i = \sum_{i=1}^{2n-3}i = \frac{(2n-3)(2n-2)}{2}.</cmath>
+Now we can compute
+<cmath>\begin{align*}
+\sum_{1\leq i < j \leq 2n-1} |F_i \cap F_j| &= 2n \cdot (2n - 2) \cdot (2n - 4)! \cdot \frac{(2n - 3)(2n - 2)}{2} \\
+&= \frac{2n \cdot (2n-2)^2 \cdot (2n - 3)!}{2} = \frac{(2n)!}{2} \cdot \frac{2n - 2}{2n - 1} \\
+&< \frac{(2n)!}{2}.
+\end{align*}</cmath>
+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 \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>.
+==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}}
 [[Category:Olympiad Combinatorics Problems]]

1989 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search