Difference between revisions of "2007 USAMO Problems/Problem 3"
(→Solution) |
|||
Line 6: | Line 6: | ||
{{USAMO newbox|year=2007|num-b=2|num-a=4}} | {{USAMO newbox|year=2007|num-b=2|num-a=4}} | ||
+ | |||
+ | Call an <math>n+1</math>-element subset of <math>S</math> seperable if it has a subset in each class of the partition. We recursively build a set <math>Q</math> of disjoint seperable subsets of <math>S</math>: begin with <math>Q</math> empty and at each step if there is a seperable subset which is disjoint from all sets in <math>Q</math> add that set to <math>Q</math>. The process terminates when every seperable 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>. | ||
+ | |||
+ | Suppose that <math>a_1, a_2, \ldots a_k</math> are elements of <math>T</math>. Denote by <math>A_i</math> the set <math>\left\{a_i, a_{i+1}, \ldots a_{i+n-1}\right\}</math>. Note that for each <math>i</math>, <math>A_i \cup A_{i+1}</math> is not seperable, so that <math>A_i</math> and <math>A_{i+1}</math> are in the same class. But then <math>A_i</math> is in the same class for each <math>1 \leq i \leq k - n + 1</math>--in particular, <math>A_1</math> and <math>A_{k-n+1}</math> are in the same class. But for any two sets we may construct such a sequence with <math>A_1</math> equal to one and <math>A_{k-n+1}</math> equal to the other. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | Idea from K81o7, write-up by 101101101. |
Revision as of 00:07, 26 April 2007
Problem
Let be a set containing
elements, for some positive integer
. Suppose that the
-element subsets of
are partitioned into two classes. Prove that there are at least
pairwise disjoint sets in the same class.
Solution
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
Call an -element subset of
seperable if it has a subset in each class of the partition. We recursively build a set
of disjoint seperable subsets of
: begin with
empty and at each step if there is a seperable subset which is disjoint from all sets in
add that set to
. The process terminates when every seperable subset intersects a set in
. Let
be the set of elements in
which are not in any set in
. We claim that one class contains every
-element subset of
.
Suppose that are elements of
. Denote by
the set
. Note that for each
,
is not seperable, so that
and
are in the same class. But then
is in the same class for each
--in particular,
and
are in the same class. But for any two sets we may construct such a sequence with
equal to one and
equal to the other.
We are now ready to construct our disjoint sets. Suppose that
. Then
, so we may select
disjoint
-element subsets of
. Then for each of the
sets in
, we may select a subset which is in the same class as all the subsets of
, for a total of
disjoint sets.
Idea from K81o7, write-up by 101101101.