Difference between revisions of "2007 USAMO Problems/Problem 3"

Revision as of 04:58, 7 August 2014

Problem

(András Gyárfás) Let $S$ be a set containing $n^2+n-1$ elements, for some positive integer $n$ . Suppose that the $n$ -element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class.

Solution

Solution 1

Call an $n+1$ -element subset of $S$ separable if it has a subset in each class of the partition. We recursively build a set $Q$ of disjoint separable subsets of $S$ : begin with $Q$ empty and at each step if there is a separable subset which is disjoint from all sets in $Q$ add that set to $Q$ . The process terminates when every separable subset intersects a set in $Q$ . Let $T$ be the set of elements in $S$ which are not in any set in $Q$ . We claim that one class contains every $n$ -element subset of $T$ .

Suppose that $a_1, a_2, \ldots a_k$ are elements of $T$ . Denote by $A_i$ the set $\left\{a_i, a_{i+1}, \ldots a_{i+n-1}\right\}$ . Note that for each $i$ , $A_i \cup A_{i+1}$ is not separable, so that $A_i$ and $A_{i+1}$ are in the same class. But then $A_i$ is in the same class for each $1 \leq i \leq k - n + 1$ — in particular, $A_1$ and $A_{k-n+1}$ are in the same class. But for any two sets we may construct such a sequence with $A_1$ equal to one and $A_{k-n+1}$ equal to the other.

We are now ready to construct our $n$ disjoint sets. Suppose that $|Q| = q$ . Then $|T| = (n+1)(n-q) - 1 \geq n(n-q)$ , so we may select $n - q$ disjoint $n$ -element subsets of $T$ . Then for each of the $q$ sets in $Q$ , we may select a subset which is in the same class as all the subsets of $T$ , for a total of $n$ disjoint sets.

Solution 2

In order to apply induction, we generalize the result to be proved so that it reads as follows:

Proposition. If the $n$ -element subsets of a set $S$ with $(n + 1)m - 1$ elements are partitioned into two classes, then there are at least $m$ pairwise disjoint sets in the same class.

Proof. Fix $n$ and proceed by induction on $m$ . The case of $m = 1$ is trivial. Assume $m > 1$ and that the proposition is true for $m - 1$ . Let $\mathcal{P}$ be the partition of the $n$ -element subsets into two classes. If all the $n$ -element subsets belong to the same class, the result is obvious. Otherwise select two $n$ -element subsets $A$ and $B$ from different classes so that their intersection has maximal size. It is easy to see that $|A\cap B| = n - 1$ . (If $|A\cap B| = k < n - 1$ , then build $C$ from $B$ by replacing some element not in $A\cap B$ with an element of $A$ not already in $B$ . Then $|A\cap C| = k + 1$ and $|B\cap C| = n - 1$ and either $A$ and $C$ or $B$ and $C$ are in different classes.) Removing $A\cup B$ from $S$ , there are $(n + 1)(m - 1) - 1$ elements left. On this set the partition induced by $\mathcal{P}$ has, by the inductive hypothesis, $m - 1$ pairwise disjoint sets in the same class. Adding either $A$ or $B$ as appropriate gives $m$ pairwise disjoint sets in the same class. $\blacksquare$

Remark: The value $n^2 + n - 1$ is sharp. A set $S$ with $n^2 + n - 2$ elements can be split into a set $A$ with $n^2 - 1$ elements and a set $B$ of $n - 1$ elements. Let one class consist of all $n$ -element subsets of $A$ and the other consist of all $n$ -element subsets that intersect $B$ . Then neither class contains $n$ pairwise disjoint sets.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 4: / Line 4: @@
 == Solution ==
+=== Solution 1 ===
 Call an <math>n+1</math>-element subset of <math>S</math> separable if it has a subset in each class of the partition. We [[recursion|recursively]] build a set <math>Q</math> of disjoint separable subsets of <math>S</math>: begin with <math>Q</math> empty and at each step if there is a separable subset which is disjoint from all sets in <math>Q</math> add that set to <math>Q</math>. The process terminates when every separable subset intersects a set in <math>Q</math>. Let <math>T</math> be the set of elements in <math>S</math> which are not in any set in <math>Q</math>. We claim that one class contains every <math>n</math>-element subset of <math>T</math>.
@@ Line 9: / Line 10: @@
 We are now ready to construct our <math>n</math> disjoint sets. Suppose that <math>|Q| = q</math>. Then <math>|T| = (n+1)(n-q) - 1 \geq n(n-q)</math>, so we may select <math>n - q</math> disjoint <math>n</math>-element subsets of <math>T</math>. Then for each of the <math>q</math> sets in <math>Q</math>, we may select a subset which is in the same class as all the subsets of <math>T</math>, for a total of <math>n</math> disjoint sets.
+=== Solution 2 ===
+In order to apply induction, we generalize the result to be proved so that it reads as follows:
+'''Proposition.''' If the <math>n</math>-element subsets of a set <math>S</math> with <math>(n + 1)m - 1</math> elements are partitioned into two classes, then there are at least <math>m</math> pairwise disjoint sets in the same class.
+''Proof.'' Fix <math>n</math> and proceed by induction on <math>m</math>. The case of <math>m = 1</math> is trivial. Assume <math>m > 1</math> and that the proposition is true for <math>m - 1</math>. Let <math>\mathcal{P}</math> be the partition of the <math>n</math>-element subsets into two classes. If all the <math>n</math>-element subsets belong to the same class, the result is obvious. Otherwise select two <math>n</math>-element subsets <math>A</math> and <math>B</math> from different classes so that their intersection has maximal size. It is easy to see that <math>|A\cap B| = n - 1</math>. (If <math>|A\cap B| = k < n - 1</math>, then build <math>C</math> from <math>B</math> by replacing some element not in <math>A\cap B</math> with an element of <math>A</math> not already in <math>B</math>. Then <math>|A\cap C| = k + 1</math> and <math>|B\cap C| = n - 1</math> and either <math>A</math> and <math>C</math> or <math>B</math> and <math>C</math> are in different classes.) Removing <math>A\cup B</math> from <math>S</math>, there are <math>(n + 1)(m - 1) - 1</math> elements left. On this set the partition induced by <math>\mathcal{P}</math> has, by the inductive hypothesis, <math>m - 1</math> pairwise disjoint sets in the same class. Adding either <math>A</math> or <math>B</math> as appropriate gives <math>m</math> pairwise disjoint sets in the same class. <math>\blacksquare</math>
+'''Remark:''' The value <math>n^2 + n - 1</math> is sharp. A set <math>S</math> with <math>n^2 + n - 2</math> elements can be split into a set <math>A</math> with <math>n^2 - 1</math> elements and a set <math>B</math> of <math>n - 1</math> elements. Let one class consist of all <math>n</math>-element subsets of <math>A</math> and the other consist of all <math>n</math>-element subsets that intersect <math>B</math>. Then neither class contains <math>n</math> pairwise disjoint sets.
+{{alternate solutions}}
 == See also ==

2007 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search