Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1989 IMO Problems/Problem 6"
(→‎Added a new solution.)
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.
 
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>.
 
So for the specific case when <math>n = 2</math>.
  
Line 127: Line 127:
  
 
<math>\mbox{Q.E.D}</math>
 
<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 > 0</math>. Let’s calculate the first two sums on the right-hand side.
 +
 +
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</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 > \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>.
  
 
== See Also == {{IMO box|year=1989|num-b=5|after=Last Question}}
 
== See Also == {{IMO box|year=1989|num-b=5|after=Last Question}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 07:27, 2 May 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 > 0$. Let’s calculate the first two sums on the right-hand side.

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$. 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 > \frac{(2n)!}{2}.\]

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

See Also

1989 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_IMO_Problems/Problem_6&oldid=192726"