From Harvard’s Math Department webpage, here’s today’s Putnam problem:
Take such that , and consider all subsets of elements of the set . Each subset has a smallest element. Let be the arithmetic mean of these smallest elements. Prove that .
For starters, note that there are
different subsets of elements of the set ; let’s denote these subsets by , where and . If the minimum element of subset is given by , we then have
This is all very nice, but computing is not that straightforward. The best way to make sure that one understands the problem at hand is to consider an example, and that’s what I will do now.
In this case, we have
different subsets of the set . Since is quite small, we can quickly and easily find all the different subsets:
and the smallest element of each subset:
And finally we have
Note that .
Let’s start by considering two extreme examples of subsets of
where . The smallest element of each of these subsets is given by
and therefore we have for every . While there’s only one subset of whose smallest element is , there is more than one subset whose smallest element is . If one can compute the number of subsets whose smallest element is , then one has solved the problem.
Let’s now consider all subsets (of elements of set ) whose smallest elements are . How many are them? If the smallest element of each of these sets is , then the remaining elements of the subset must be elements of set , whose cardinality is , and therefore we have
such subsets. If we consider all subsets whose smallest elements are (where ), then the remaning elements of these subsets must be elements of set , whose cardinality is . Therefore, there are
subsets whose smallest elements are . Note that if , we have
subset only, as I had mentioned above. Since we now know how many subsets with a specific smallest element there are, we can compute by taking the weighted average
The denominator should me equal to , and I have proved that already (I am not going to type the proof here because it’s a bit cumbersome). However, I can’t do much with the numerator. I am stuck. If you have any ideas, let me know.