1979 USAMO Problems/Problem 5

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 (ProblemsResources)
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