Difference between revisions of "2011 USAMO Problems/Problem 6"
(→Minimality) |
m (reformatting st sol 3 is above the maa notice) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 23: | Line 23: | ||
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>\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> | <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 | ||
+ | |||
+ | ==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}} | {{MAA Notice}} | ||
+ | |||
==See also== | ==See also== |
Latest revision as of 09:59, 1 August 2024
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
Solution 3
Define to be the amount of elements in
such that the element is contained exactly
times among the
subsets
. We are trying to prove that
. Now, note that
is equivalent to the total amount of not necessarily distinct elements among the subsets
, thus
. Furthermore, note that
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
times in this sum, and there are
total distinct pairs of subsets, so
. Noting that
for all nonnegative integers, we note
Finally, CS inequality gives us
as desired.
One equality case occurs when if
is not
, and
. Choose any
elements, and represent each with a unique combination of
of the
subsets (
). It is then obvious that each subset has
distinct elements, because after each subset is chosen, there are
ways to choose the other two subsets to produce a unique element. Similarly, each pair of subsets shares exactly
elements, because after choosing the two subsets, we can choose one of the remaining
subsets to produce the unique element. Hence, proved.
~SigmaPiE
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 |