Difference between revisions of "2011 USAMO Problems/Problem 6"

Revision as of 14:31, 5 May 2011

Problem

Let $A$ be a set with $|A| = 225$ , meaning that $A$ has 225 elements. Suppose further that there are eleven subsets $A_1$ , $\dots$ , $A_{11}$ of $A$ such that $|A_i | = 45$ for $1 \le i \le 11$ and $|A_i \cap A_j| = 9$ for $1 \le i < j \le 11$ . Prove that $|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165$ , and give an example for which equality holds.

Solution

Existence

Note that $\textstyle \binom{11}3 = 165,$ and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections—one with each of the 9 remaining sets—any two sets will have 9 elements in common. Since $\binom{10}2 = 45,$ each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the $A_i$ and we are done.

Minimality

As in the proof of PIE, let $I$ be a finite set. Let $U = \bigcup_{i\in I} A_i$ . For $i\in I$ , let $\chi_i$ be the characteristic function of $A_i$ , that is, for $\alpha \in U,$ $\chi_i(\alpha) = \begin{cases} 1 & \alpha \in A_i \\ 0 & \alpha \not\in A_i \end{cases}$

For each $\alpha \in U$ let $n_\alpha = \sum_{i \in I} \chi_i(\alpha)$ , that is the number of subsets $A_i$ of which $\alpha$ is an element.

If $S \subset I$ , let $A_S = \bigcap_{i \in S}A_i$ . Then the characteristic function of $A_S$ is $\prod_{i \in S} \chi_i$ . The number of elements of $A_S$ is simply the sum of its characteristic function over all the elements of $U$ : $|A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha).$ For $0 \le k \le |I|$ , consider the sum $N_k$ of $|A_S|$ over all $S\subset I$ with $|S|= k$ . This is: $N_k = \sum_{\substack{S\subset I\\|S| = k}} \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha) = \sum_{\substack{S\subset I\\|S| = k}} |A_S|$ reversing the order summation, as an element $\alpha$ that appears in $n_\alpha$ of the $A_i$ , will appear in exactly $\textstyle \binom{n_\alpha}k}$ (Error compiling LaTeX. Unknown error_msg) intersections of $k$ subsets, we get: $\sum_{\substack{S\subset I\\|S| = k}} |A_S| = \sum_{\alpha \in U} \sum_{\substack{S\subset I\\|S| = k}} \prod_{i \in S} \chi_i(\alpha) = \sum_{\alpha \in U} \binom{n_\alpha}k.$

Applying the above with $I = \{1, 2, \ldots, 11\},$ and $k=1$ , since each of the 11 $A_i$ has 45 elements, we get: $N_1 = \sum_{\alpha \in U} n_\alpha = 11 \cdot 45,$ and for $k = 2$ , since each of the 55 pairs $A_i \cap A_j$ has 9 elements, we get: $N_2 = \sum_{\alpha \in U} \binom{n_\alpha}2 = 9 \cdot 55 = 11 \cdot 45.$

Therefore $\begin{align*} s_1 &= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\ s_2 &= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45. \end{align*}$ Let $n = |U|$ be the number of elements of $U$ . Since for any set of real numbers the mean value of the squares is greater than or equal to the square of the mean value, we have: $\frac{s_2}n \ge \left(\frac{s_1}n\right)^2 \implies n \ge \frac{s_1^2}{s_2} = \frac{11^2\cdot 45^2}{3\cdot11\cdot45} = \frac{11\cdot45}3 = 165.$

Thus $|U| \ge 165$ as required.

@@ Line 5: / Line 5: @@
 ===Existence===
-Note that <math>\binom{11}3 = 165,</math> and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&mdash;one with each of the 9 remaining sets&mdash;any two sets will have 9 elements in common. Since <math>\binom{10}2 = 45,</math> each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the <math>A_i</math> and we are done.
+Note that <math>\textstyle \binom{11}3 = 165,</math> and so it is natural to consider placing one element in each intersection of three of the 11 sets. Since each pair of sets is in 9 3-way intersections&mdash;one with each of the 9 remaining sets&mdash;any two sets will have 9 elements in common. Since <math>\binom{10}2 = 45,</math> each set is in 45 triples and thus will have 45 elements. We can now throw in 60 more elements outside the union of the <math>A_i</math> and we are done.
 ===Minimality===

2011 USAMO (Problems • Resources)
Preceded by Problem 5	Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search