2011 USAMO Problems/Problem 6
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.
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.
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.
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
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
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.
|2011 USAMO (Problems • Resources)
|1 • 2 • 3 • 4 • 5 • 6
|All USAMO Problems and Solutions