2007 USAMO Problems/Problem 3

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

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.

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

2007 USAMO Problems/Problem 3

Problem

Solution

See also