Difference between revisions of "2011 USAMO Problems/Problem 6"
(Created page with '==Problem== Let <math>A</math> be a set with <math>|A| = 225</math>, meaning that <math>A</math> has 225 elements. Suppose further that there are eleven subsets <math>A_1</math>…') |
(→Solution) |
||
Line 22: | Line 22: | ||
<cmath> |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). </cmath> | <cmath> |A_S| = \sum_{\alpha \in U} \prod_{i \in S} \chi_i(\alpha). </cmath> | ||
For <math>0 \le k \le |I|</math>, consider the sum <math>N_k</math> of <math>|A_S|</math> over all <math>S\subset I</math> with <math>|S|= k</math>. This is: | For <math>0 \le k \le |I|</math>, consider the sum <math>N_k</math> of <math>|A_S|</math> over all <math>S\subset I</math> with <math>|S|= k</math>. This is: | ||
− | <cmath> | + | <cmath> 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| </cmath> |
− | 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| | ||
− | </cmath> | ||
reversing the order summation, we get: | reversing the order summation, we get: | ||
− | <cmath> | + | <cmath>\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 </cmath> since an element <math>\alpha</math> that appears in <math>n_\alpha</math> of the <math>A_i</math>, will appear in exactly <math>\binom{n_\alpha}k</math> intersections of <math>k</math> subsets. |
− | \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 | ||
− | </cmath> | ||
− | since an element <math>\alpha</math> that appears in <math>n_\alpha</math> of the <math>A_i</math>, will appear in exactly <math>\binom{n_\alpha}k</math> intersections of <math>k</math> subsets. | ||
Applying the above with <math>I = \{1, 2, \ldots, 11\},</math> and <math>k=1</math>, since each of the 11 <math>A_i</math> has 45 elements, we get: | Applying the above with <math>I = \{1, 2, \ldots, 11\},</math> and <math>k=1</math>, since each of the 11 <math>A_i</math> has 45 elements, we get: | ||
Line 37: | Line 32: | ||
Therefore | Therefore | ||
− | <cmath> | + | <cmath>\begin{align*} |
− | \begin{align*} | ||
s_1 &= \sum_{\alpha \in U} n_\alpha = N_1 = 11\cdot45 \\ | 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. | s_2 &= \sum_{\alpha \in U} n_\alpha^2 = 2N_2 + N_1 = 3\cdot11\cdot45. | ||
− | \end{align*} | + | \end{align*}</cmath> |
− | </cmath> | ||
Let <math>n = |U|</math> be the number of elements of <math>U</math>. | Let <math>n = |U|</math> be the number of elements of <math>U</math>. | ||
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: | 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: | ||
− | <cmath> \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.</cmath> | + | <cmath>\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.</cmath> |
Thus <math>|U| \ge 165</math> as required. | Thus <math>|U| \ge 165</math> as required. |
Revision as of 14:28, 5 May 2011
Problem
Let be a set with , meaning that has 225 elements. Suppose further that there are eleven subsets , , of such that for and for . Prove that , and give an example for which equality holds.
Solution
Existence
Note that 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 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 and we are done.
Minimality
As in the proof of PIE, let be a finite set. Let . For , let be the characteristic function of , that is, for
For each let , that is the number of subsets of which is an element.
If , let . Then the characteristic function of is . The number of elements of is simply the sum of its characteristic function over all the elements of : For , consider the sum of over all with . This is: reversing the order summation, we get: since an element that appears in of the , will appear in exactly intersections of subsets.
Applying the above with and , since each of the 11 has 45 elements, we get: and for , since each of the 55 pairs has 9 elements, we get:
Therefore Let be the number of elements of . 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:
Thus as required.
See also
2011 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |