Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1979 USAMO Problems/Problem 5"

(→‎Problem)
 
(4 intermediate revisions by 4 users not shown)
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 =|A_n|=3</math>.  Prove that <math>|A_i\cap A_j|=1</math> for some pair <math>\{i,j\}</math>.
+
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==
 +
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>.
  
−
{{USAMO box|year=1979|num-b=4|after=Last Problem}}
+
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==
 +
{{USAMO box|year=1979|num-b=4|after=Last Question}}
 +
{{MAA Notice}}
 +
 
 +
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 20:04, 11 November 2015

Problem

Let $A_1,A_2,...,A_{n+1}$ be distinct subsets of $[n]$ with $|A_1|=|A_2|=\cdots =|A_{n+1}|=3$. Prove that $|A_i\cap A_j|=1$ for some pair $\{i,j\}$.

Solution

Suppose the problem statement does not hold. It is clear that $n \ge 4$. Choose the smallest $n$ such that $|A_i \cap A_j| \neq 1$ for each $\{i, j\}$.

First, the $(n+1)$ subsets have $3(n+1)$ elements (some repeated) in conjunction. Because there are $n$ elements of $[n]$ total, by the Pigeonhole Principle one element of $[n]$, say $k$, is in at least four subsets. Let these subsets be $A_1, A_2, A_3, A_4$, without loss of generality, and let $A_1$ have elements $k, m, n$. Then without loss of generality let $A_2$ have elements $k, m, p$. If set $A_3$ has elements $k, n, p$, then simple casework shows that it is impossible to create $A_4$ without having $A_4$ intersect one of $A_1, A_2, A_3$ at exactly one element. Thus assume $A_3$ has elements $k, m, q$. Then $A_4$ has elements $k, m, r$. Consider each remaining set $A_i$. Then $A_i$ either contains both $k, m$ or none of them. Because there are $(n-2)$ distinct elements of $[n]$ apart from $k, m$, at most $(n-2)$ subsets can contain $k, m$. Then at least 3 subsets do not contain $k, m$, and it is easy to see that they are disjoint from those subsets that do contain $k, m$. Thus, we can partition $[n]$ into two subsets, one of which is the union of the $t$ subsets that do contain $k, m$, and the other is the union of the $(n+1)-t$ subsets that do not contain $k, m$. Because the latter subset has $(n-t-2) < (n+1)-t - 1$ elements, we may use infinite descent to contradict the minimality of $n$. 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1979_USAMO_Problems/Problem_5&oldid=72894"