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

Latest revision as of 08:59, 1 August 2024

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 $\textstyle \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 $\textstyle 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 $\textstyle 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 $\textstyle A_S = \bigcap_{i \in S}A_i$ . Then the characteristic function of $A_S$ is $\textstyle \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}$ 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.

Solution 2

We will count the number of ordered triples, $(A_i,A_j,x)$ , where $1\le i,j\le11$ and $x\in A_i \cap A_j$ . We know this is equal to $990=11\cdot10\cdot9$ . We can also find that this is $\sum_{k=1}^{225}b_k^2-b_k$ , where $b_k$ is the number of the $11$ subsets the $k^{\text{th}}$ element of $A$ is in. Since $\sum_{k=1}^{225}b_k=45\cdot11=495$ , we know $\sum_{k=1}^{225}b_k^2=990+495=1485$ . Let $n=|A_1 \cup A_2 \cup \dots \cup A_{11}|$ . $n$ is equal to the number of $b_k>0$ , where $1\le k\le225$ . By the QM-AM inequality, we know $\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$ and that equality occurs when $b_1=b_2=b_3=\cdots=b_{165}=3,b_{166}=b_{167}=\cdots=b_{225}=0$ . $\square$

Solution by randomdude10807

Solution 3

Define $x_i$ to be the amount of elements in $A$ such that the element is contained exactly $i$ times among the $11$ subsets $A_j$ . We are trying to prove that $\sum_{i=1}^{11}x_i\ge 165$ . Now, note that $\sum_{i=1}^{11}ix_i$ is equivalent to the total amount of not necessarily distinct elements among the subsets $A_j$ , thus $\sum_{i=1}^{11}ix_i=11|A_j|=495$ . Furthermore, note that $\sum_{i=1}^{11}\binom{i}{2}x_i$ is equivalent to the total amount of not necessarily distinct pairs of subsets such that the subsets share an element. In other words, each subset pair should be counted $9$ times in this sum, and there are $\binom{11}{2}$ total distinct pairs of subsets, so $\sum_{i=1}^{11}\binom{i}{2}x_i=9*\binom{11}{2}=495$ . Noting that $2\binom{i}{2}+i=i^2$ for all nonnegative integers, we note

$\sum_{i=1}^{11}i^2x_i=2(\sum_{i=1}^{11}\binom{i}{2}x_i)+(\sum_{i=1}^{11}ix_i)=495*2+495=495*3$

Finally, CS inequality gives us

$(\sum_{i=1}^{11}i^2x_i)(\sum_{i=1}^{11}x_i)\ge(\sum_{i=1}^{11}ix_i)^2$ $(495*3)(\sum_{i=1}^{11}x_i)\ge(495^2)$ $\boxed{(\sum_{i=1}^{11}x_i)\ge 165}$ as desired.

One equality case occurs when $x_i=0$ if $i$ is not $3$ , and $x_3=165$ . Choose any $165$ elements, and represent each with a unique combination of $3$ of the $11$ subsets ( $\binom{11}{3}=165$ ). It is then obvious that each subset has $45$ distinct elements, because after each subset is chosen, there are $\binom{10}{2}=45$ ways to choose the other two subsets to produce a unique element. Similarly, each pair of subsets shares exactly $9$ elements, because after choosing the two subsets, we can choose one of the remaining $9$ subsets to produce the unique element. Hence, proved. $\blacksquare{}$

~SigmaPiE

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

@@ Line 8: / Line 8: @@
 ===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>
 \chi_i(\alpha) = \begin{cases}
@@ Line 16: / Line 16: @@
 </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>:
 <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:
 <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>\textstyle \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>
@@ Line 41: / Line 41: @@
 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
+==Solution 3==
+Define <math>x_i</math> to be the amount of elements in <math>A</math> such that the element is contained exactly <math>i</math> times among the <math>11</math> subsets <math>A_j</math>. We are trying to prove that <math>\sum_{i=1}^{11}x_i\ge 165</math>. Now, note that <math>\sum_{i=1}^{11}ix_i</math> is equivalent to the total amount of not necessarily distinct elements among the subsets <math>A_j</math>, thus <math>\sum_{i=1}^{11}ix_i=11|A_j|=495</math>. Furthermore, note that <math>\sum_{i=1}^{11}\binom{i}{2}x_i</math> is equivalent to the total amount of not necessarily distinct pairs of subsets such that the subsets share an element. In other words, each subset pair should be counted <math>9</math> times in this sum, and there are <math>\binom{11}{2}</math> total distinct pairs of subsets, so <math>\sum_{i=1}^{11}\binom{i}{2}x_i=9*\binom{11}{2}=495</math>. Noting that <math>2\binom{i}{2}+i=i^2</math> for all nonnegative integers, we note
+<cmath>\sum_{i=1}^{11}i^2x_i=2(\sum_{i=1}^{11}\binom{i}{2}x_i)+(\sum_{i=1}^{11}ix_i)=495*2+495=495*3</cmath>
+Finally, CS inequality gives us
+<cmath>(\sum_{i=1}^{11}i^2x_i)(\sum_{i=1}^{11}x_i)\ge(\sum_{i=1}^{11}ix_i)^2</cmath>
+<cmath>(495*3)(\sum_{i=1}^{11}x_i)\ge(495^2)</cmath>
+<cmath>\boxed{(\sum_{i=1}^{11}x_i)\ge 165}</cmath>
+as desired.
+One equality case occurs when <math>x_i=0</math> if <math>i</math> is not <math>3</math>, and <math>x_3=165</math>. Choose any <math>165</math> elements, and represent each with a unique combination of <math>3</math> of the <math>11</math> subsets (<math>\binom{11}{3}=165</math>). It is then obvious that each subset has <math>45</math> distinct elements, because after each subset is chosen, there are <math>\binom{10}{2}=45</math> ways to choose the other two subsets to produce a unique element. Similarly, each pair of subsets shares exactly <math>9</math> elements, because after choosing the two subsets, we can choose one of the remaining <math>9</math> subsets to produce the unique element. Hence, proved. <math>\blacksquare{}</math>
+~SigmaPiE
+{{MAA Notice}}
 ==See also==

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

Page

Toolbox

Search