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"
 
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==

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"