Library / /68 of 91

, 2006

Combinatorics Difficulty 6.8 National Olympiad Prove it India

Let $A_1, A_2, A_3, \dots, A_n$ be $n$ subsets of a finite set $S$ such that $|A_j| = 8$ for each $j$ , $1 \le j \le n$ . For a subset $B$ of $S$ , let $F(B) = \{j : 1 \le j \le n \text{ and } A_j \subset B\}$ . Suppose for each subset $B$ of $S$ , at least one of the following conditions holds:
(i) $|B| > 25$ ;
(ii) $F(B) = \emptyset$ ;
(iii) $\cap_{j \in F(B)} A_j \ne \emptyset$ .

Prove that $A_1 \cap A_2 \cap A_3 \cap \dots \cap A_n \ne \emptyset$ .

Solution

We use induction on $n$ . The case $n = 1$ is immediate. Assume the result for $n$ and consider the case of $n+1$ . Thus $A_1, A_2, \dots, A_{n+1}$ are subsets of $S$ with $|A_j| = 8$ .
Now if we consider the sets $A_1, A_2, \dots, A_{j-1}, A_{j+1}, \dots, A_{n+1}$ , these satisfy induction hypothesis for each $j = 1, 2, 3, \dots, n+1$ . Hence there exists
$x_j \in A_1 \cap A_2 \cap \dots \cap A_{j-1} \cap A_{j+1} \cap \dots \cap A_{n+1},$
for each $j = 1, 2, \dots, n+1$ . If $x_1, x_2, \dots, x_{n+1}$ are not all distinct, then we are through. Suppose they are all distinct. Consider $B = A_1 \cup A_2 \cup \dots \cup A_{n+1}$ . We show that $|B| \le 25$ . Note that each $x_j$ is over counted $n-1$ times in the union. Thus
$|B| \le |A_1| + |A_2| + \dots + |A_{n+1}| - (n-1)(n+1) = 8(n+1) - (n^2-1) \le 25,$
since $n^2 - 8n + 16 = (n-4)^2 \ge 0$ . Thus the condition (i) fails. Clearly, the condition (2) also fails. Hence (iii) must hold.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.