Difference between revisions of "1979 USAMO Problems/Problem 5"
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Let <math>A_1,A_2,...,A_{n+1}</math> be distinct subsets of <math>[n]</math> with <math>|A_1|=|A_2|=\cdots =| | + | Let <math>A_1,A_2,...,A_{n+1}</math> be distinct subsets of <math>[n]</math> with <math>|A_1|=|A_2|=\cdots =|A_{n+1}|=3</math>. Prove that <math>|A_i\cap A_j|=1</math> for some pair <math>\{i,j\}</math>. |
==Solution== | ==Solution== |
Latest revision as of 21:04, 11 November 2015
Problem
Let be distinct subsets of
with
. Prove that
for some pair
.
Solution
Suppose the problem statement does not hold. It is clear that . Choose the smallest
such that
for each
.
First, the subsets have
elements (some repeated) in conjunction. Because there are
elements of
total, by the Pigeonhole Principle one element of
, say
, is in at least four subsets. Let these subsets be
, without loss of generality, and let
have elements
. Then without loss of generality let
have elements
. If set
has elements
, then simple casework shows that it is impossible to create
without having
intersect one of
at exactly one element. Thus assume
has elements
. Then
has elements
. Consider each remaining set
. Then
either contains both
or none of them. Because there are
distinct elements of
apart from
, at most
subsets can contain
. Then at least 3 subsets do not contain
, and it is easy to see that they are disjoint from those subsets that do contain
. Thus, we can partition
into two subsets, one of which is the union of the
subsets that do contain
, and the other is the union of the
subsets that do not contain
. Because the latter subset has
elements, we may use infinite descent to contradict the minimality of
. The proof is complete.
See Also
1979 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.