Difference between revisions of "2011 USAMO Problems/Problem 6"
(→Minimality) |
(Added second solution) |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 5: | Line 5: | ||
===Existence=== | ===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—one with each of the 9 remaining sets—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—one with each of the 9 remaining sets—any two sets will have 9 elements in common. Since <math>\textstyle \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=== | ===Minimality=== | ||
− | As in the proof of PIE, let <math>I</math> be a finite set. Let <math>U = \bigcup_{i\in I} A_i</math>. For <math>i\in I</math>, let <math>\chi_i</math> be the <i>characteristic function</i> of <math>A_i</math>, that is, for <math>\alpha \in U,</math> | + | As in the proof of PIE, let <math>I</math> be a finite set. Let <math>\textstyle U = \bigcup_{i\in I} A_i</math>. For <math>i\in I</math>, let <math>\chi_i</math> be the <i>characteristic function</i> of <math>A_i</math>, that is, for <math>\alpha \in U,</math> |
<cmath> | <cmath> | ||
\chi_i(\alpha) = \begin{cases} | \chi_i(\alpha) = \begin{cases} | ||
Line 16: | Line 16: | ||
</cmath> | </cmath> | ||
− | For each <math>\alpha \in U</math> let <math>n_\alpha = \sum_{i \in I} \chi_i(\alpha)</math>, that is the number of subsets <math>A_i</math> of which <math>\alpha</math> is an element. | + | For each <math>\alpha \in U</math> let <math>\textstyle n_\alpha = \sum_{i \in I} \chi_i(\alpha)</math>, that is the number of subsets <math>A_i</math> of which <math>\alpha</math> is an element. |
− | If <math>S \subset I</math>, let <math>A_S = \bigcap_{i \in S}A_i</math>. Then the characteristic function of <math>A_S</math> is <math>\prod_{i \in S} \chi_i</math>. | + | If <math>S \subset I</math>, let <math>\textstyle A_S = \bigcap_{i \in S}A_i</math>. Then the characteristic function of <math>A_S</math> is <math>\textstyle \prod_{i \in S} \chi_i</math>. |
The number of elements of <math>A_S</math> is simply the sum of its characteristic function over all the elements of <math>U</math>: | The number of elements of <math>A_S</math> is simply the sum of its characteristic function over all the elements of <math>U</math>: | ||
<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> 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> | <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, as 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, we get: | + | reversing the order summation, as an element <math>\alpha</math> that appears in <math>n_\alpha</math> of the <math>A_i</math>, will appear in exactly <math>\textstyle \binom{n_\alpha}{k}</math> intersections of <math>k</math> subsets, we get: |
<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> | <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> | ||
Line 41: | Line 41: | ||
Thus <math>|U| \ge 165</math> as required. | Thus <math>|U| \ge 165</math> as required. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | We will count the number of ordered triples, <math>(A_i,A_j,x)</math>, where <math>1\le i,j\le11</math> and <math>x\in A_i \cap A_j</math>. We know this is equal to <math>990=11\cdot10\cdot9</math>. We can also find that this is <math>\sum_{k=1}^{225}b_k^2-b_k</math>, where <math>b_k</math> is the number of the <math>11</math> subsets the <math>k^{\text{th}}</math> element of <math>A</math> is in. Since <math>\sum_{k=1}^{225}b_k=45\cdot11=495</math>, we know <math>\sum_{k=1}^{225}b_k^2=990+495=1485</math>. Let <math>n=|A_1 \cup A_2 \cup \dots \cup A_{11}|</math>. <math>n</math> is equal to the number of <math>b_k>0</math>, where <math>1\le k\le225</math>. By the QM-AM inequality, we know <math>\frac{\sum_{k=1}^{225}b_k^2}n\ge\Bigg(\frac{\sum_{k=1}^{225}b_k}n\Bigg)^2\implies\frac{1485}n\ge\Big(\frac{495}n\Big)^2\implies n\ge165</math> and that equality occurs when <math>b_1=b_2=b_3=\cdots=b_{165}=3,b_{166}=b_{167}=\cdots=b_{225}=0</math>. | ||
+ | <math>\square</math> | ||
+ | |||
+ | Solution by randomdude10807 | ||
+ | |||
+ | {{MAA Notice}} | ||
==See also== | ==See also== |
Latest revision as of 08:17, 27 February 2018
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, as an element that appears in of the , will appear in exactly intersections of subsets, we get:
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.
Solution 2
We will count the number of ordered triples, , where and . We know this is equal to . We can also find that this is , where is the number of the subsets the element of is in. Since , we know . Let . is equal to the number of , where . By the QM-AM inequality, we know and that equality occurs when .
Solution by randomdude10807
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2011 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |