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

1979 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1979 USAMO Problems/Problem 5

Problem

Solution

See Also