Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Minimality)
(Added second solution)
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}}
 
{{MAA Notice}}

Revision as of 08:17, 27 February 2018

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

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

See also

2011 USAMO (Problems • Resources)
Preceded by
Problem 5 		Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_6&oldid=92410"