For integer , let be real numbers satisfying
For each subset , define
(If is the empty set, then .)
Prove that for any positive number , the number of sets satisfying is at most .
For what choices of does equality hold?
Solution
This problem is a form of Chebyshev's inequality for random variables. For each subset , define
where if and otherwise. Squaring, we have
Now sum the 's over all possible choices of . For each pair , there are sets with , and another sets with ; these sets each contribute a term of to the sum in (10). There are also sets with , , and sets with , . Each of these sets contributes a term of to (10). Hence appears times with a sign and times with a sign. Therefore all of these terms cancel, and we obtain
Now let . There cannot be more than terms whose value greater than or equal to . If this were not the case, then the sum of these terms would be greater than , so the sum in (11) would exceed . Hence, there can be at most sets such that . (Recall that .) Moreover, these sets can be arranged into complementary pairs because . In each of these pairs, exactly one of the two members is positive. Therefore there are at most sets with .
For equality to hold, it must be the case that all positive values of are equal to ; otherwise we would again have a contradiction because the sum of all would exceed . In particular, all positive values of must be the same. Thus, all positive values of must be the same. This will be the case only if at most one of the is positive and at most one of the is negative. Because we must have at least one of each, there must be exactly one positive term and one negative term. Thus, it must be the case that for some , for some , and for . Then the assumption that every positive yields .
Conversely, with the and as described, we have exactly sets such that : namely, the sets that contain the term and do not contain the term. Thus, this is indeed the equality case.