Let be integers, let be a set with elements, and let be pairwise distinct non-empty, not necessarily disjoint subsets of . A function is called nice if there exists an index such that
Prove that the number of nice functions is at least . (Germany)
Solution
For a subset , we write for . Note that a function is nice, if and only if is maximized by a unique index . We will first investigate the set of functions ; note that . For every function , define a corresponding function in the following way: Pick some set that maximizes the value .
- For all , define .
- For all , define .
Claim. The resulting function is nice.
Proof. Note that holds for all . We show that is maximized at the unique index . Hence consider some arbitrary index . Then is impossible, as this would imply and thereby contradict the choice of set ; this in particular yields .
The first inequality follows since was chosen to maximize the value . The second (strict) inequality follows from as observed above. This completes the proof of the claim.
Next observe that function can be uniquely reconstructed from : the claim yields that has a unique maximizer , and by decreasing the value of on by 1, we get we can fully determine the values of . As each of the functions yields a (unique) corresponding nice function , the proof is complete.