Difference between revisions of "2007 USAMO Problems/Problem 3"
5849206328x (talk | contribs) m (→See also) |
5849206328x (talk | contribs) m (→Problem) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | + | (''András Gyárfás'') Let <math>S</math> be a [[set]] containing <math>n^2+n-1</math> [[element]]s, for some [[positive]] [[integer]] <math>n</math>. Suppose that the <math>n</math>-element [[subset]]s of <math>S</math> are partitioned into two classes. Prove that there are at least <math>n</math> [[pairwise disjoint]] sets in the same class. | |
− | Let <math>S</math> be a [[set]] containing <math>n^2+n-1</math> [[element]]s, for some [[positive]] [[integer]] <math>n</math>. Suppose that the <math>n</math>-element [[subset]]s of <math>S</math> are partitioned into two classes. Prove that there are at least <math>n</math> [[pairwise disjoint]] sets in the same class. | ||
== Solution == | == Solution == |
Revision as of 04:37, 7 August 2014
Problem
(András Gyárfás) 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
Call an -element subset of
separable if it has a subset in each class of the partition. We recursively build a set
of disjoint separable subsets of
: begin with
empty and at each step if there is a separable subset which is disjoint from all sets in
add that set to
. The process terminates when every separable 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 separable, 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.
See also
- <url>viewtopic.php?t=145845 Discussion on AoPS/MathLinks</url>
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.