Difference between revisions of "1979 USAMO Problems/Problem 5"
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| − | { | + | Suppose the problem statement does not hold. It is clear that <math>n \ge 4</math>. Choose the smallest <math>n</math> such that <math>|A_i \cap A_j| \neq 1</math> for each <math>\{i, j\}</math>. |
| + | |||
| + | First, the <math>(n+1)</math> subsets have <math>3(n+1)</math> elements (some repeated) in conjunction. Because there are <math>n</math> elements of <math>[n]</math> total, by the Pigeonhole Principle one element of <math>[n]</math>, say <math>k</math>, is in at least four subsets. Let these subsets be <math>A_1, A_2, A_3, A_4</math>, without loss of generality, and let <math>A_1</math> have elements <math>k, m, n</math>. Then without loss of generality let <math>A_2</math> have elements <math>k, m, p</math>. If set <math>A_3</math> has elements <math>k, n, p</math>, then simple casework shows that it is impossible to create <math>A_4</math> without having <math>A_4</math> intersect one of <math>A_1, A_2, A_3</math> at exactly one element. Thus assume <math>A_3</math> has elements <math>k, m, q</math>. Then <math>A_4</math> has elements <math>k, m, r</math>. Consider each remaining set <math>A_i</math>. Then <math>A_i</math> either contains both <math>k, m</math> or none of them. Because there are <math>(n-2)</math> distinct elements of <math>[n]</math> apart from <math>k, m</math>, at most <math>(n-2)</math> subsets can contain <math>k, m</math>. Then at least 3 subsets do not contain <math>k, m</math>, and it is easy to see that they are disjoint from those subsets that do contain <math>k, m</math>. Thus, we can partition <math>[n]</math> into two subsets, one of which is the union of the <math>t</math> subsets that do contain <math>k, m</math>, and the other is the union of the <math>(n+1)-t</math> subsets that do not contain <math>k, m</math>. Because the latter subset has <math>(n-t-2) < (n+1)-t - 1</math> elements, we may use infinite descent to contradict the minimality of <math>n</math>. The proof is complete. | ||
==See Also== | ==See Also== | ||
{{USAMO box|year=1979|num-b=4|after=Last Question}} | {{USAMO box|year=1979|num-b=4|after=Last Question}} | ||
Revision as of 20:02, 16 June 2015
Problem
Let 
be distinct subsets of ![$[n]$](http://latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
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. 
