Problem:
For integer n≥2, let x1​,x2​,…,xn​ be real numbers satisfying
x1​+x2​+⋯+xn​=0, and x12​+x22​+⋯+xn2​=1
For each subset A⊆{1,2,…,n}, define
SA​=i∈A∑​xi​
(If A is the empty set, then SA​=0.)
Prove that for any positive number λ, the number of sets A satisfying SA​≥λ is at most 2n−3/λ2. For what choices of x1​,x2​,…,xn​,λ does equality hold?
Solution:
This problem is a form of Chebyshev's inequality for random variables. For each set A⊆{1,2,…,n}, define
Now sum the ΔA2​ 's over all 2n possible choices of A. For each pair iî€ =j, there are 2n−2 sets A with i,j∈A, and another 2n−2 sets with i,j∈/A; these sets each contributes a term of +xi​xj​ to the sum in (6). There are also 2n−2 sets A with i∈A,j∈/A, and 2n−2 sets with i∈/A,j∈A. Each of these sets each contributes a term of −xi​xj​ to (6). Hence, xi​xj​ appears 2n−1 times with a + sign and 2n−1 times with a− sign. Therefore all of these terms cancel, and we find
Now let λ>0. There cannot be more than 2n−2/λ2 terms ΔA2​ whose value greater than or equal to 4λ2. If this were not the case, then the sum of these terms would be greater than 2n, so the sum in (7) would exceed 2n. Hence, there can be at most 2n−2/λ2 sets A such that ∣SA​∣≥λ. (Recall that ΔA​=2SA​ ). Moreover, these sets can be arranged into complementary pairs because SA​=−S{1,…,n}\A​. In each of these pairs, exactly one of the two members is positive. Therefore there are at most 2n−3/λ2 sets A with SA​≥λ.
For equality to hold, it must be the case that all positive values of ΔA2​ are equal to 4λ2; otherwise we would again have a contradiction because the sum of all ΔA2​ would exceed 2n. In particular, all positive values of ΔA2​ must be the same. Thus all positive values of xA​ must be the same. This will be the case only if at most one of the xi​ is positive and at most one of the xi​ 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 one xk​=2​/2 for some k, one is xj​=−2​/2 for some jî€ =k, and all other xi​=0. Then the assumption that every positive ΔA2​=4λ2 yields λ=2​/2.
Conversely, with the xi​ and λ as described, we have exactly 2n−2=2n−3/λ2 sets A such that xA​≥λ (namely, those sets A that contain the 2​/2 term and do not contain the −2​/2 term.) Thus this is indeed the equality case.
This problem and solution were suggested by Gabriel Carroll.