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