Maths Olympiad Prep

Library / /162 of 169

Combinatorics Difficulty 8.0 Shortlist Prove it United States

For integer n2n \ge 2, let x1,x2,,xnx_1, x_2, \dots, x_n be real numbers satisfying
x1+x2++xn=0,andx12+x22++xn2=1. x_1 + x_2 + \dots + x_n = 0, \quad \text{and} \quad x_1^2 + x_2^2 + \dots + x_n^2 = 1.
For each subset A{1,2,,n}A \subseteq \{1, 2, \dots, n\}, define
SA=iAxi. S_A = \sum_{i \in A} x_i.
(If AA is the empty set, then SA=0S_A = 0.)
Prove that for any positive number λ\lambda, the number of sets AA satisfying SAλS_A \ge \lambda is at most 2n3λ2\frac{2^{n-3}}{\lambda^2}.
For what choices of x1,x2,,xn,λx_1, x_2, \dots, x_n, \lambda does equality hold?

Solution

This problem is a form of Chebyshev's inequality for random variables. For each subset A{1,2,,n}A \subseteq \{1, 2, \dots, n\}, define
ΔA=2SA=iAxii{1,2,,n}Axi=i=1nϵA(i)xi, \Delta_A = 2S_A = \sum_{i \in A} x_i - \sum_{i \in \{1, 2, \dots, n\} \setminus A} x_i = \sum_{i=1}^n \epsilon_A(i)x_i,
where ϵA(i)=1\epsilon_A(i) = 1 if iAi \in A and ϵA(i)=1\epsilon_A(i) = -1 otherwise. Squaring, we have
ΔA2=i=1nxi2+i,j{1,,n}ijϵA(i)ϵA(j)xixj.(10) \Delta_A^2 = \sum_{i=1}^n x_i^2 + \sum_{\substack{i,j \in \{1, \dots, n\} \\ i \neq j}} \epsilon_A(i)\epsilon_A(j)x_i x_j. \quad (10)
Now sum the ΔA2\Delta_A^2's over all 2n2^n possible choices of AA. For each pair iji \neq j, there are 2n22^{n-2} sets AA with i,jAi, j \in A, and another 2n22^{n-2} sets with i,jAi, j \notin A; these sets each contribute a term of +xixj+x_i x_j to the sum in (10). There are also 2n22^{n-2} sets AA with iAi \in A, jAj \notin A, and 2n22^{n-2} sets with iAi \notin A, jAj \in A. Each of these sets contributes a term of xixj-x_i x_j to (10). Hence xixjx_i x_j appears 2n12^{n-1} times with a ++ sign and 2n12^{n-1} times with a - sign. Therefore all of these terms cancel, and we obtain
A{1,2,,n}ΔA2=2n(x12++xn2)=2n.(11) \sum_{A \subseteq \{1, 2, \dots, n\}} \Delta_A^2 = 2^n (x_1^2 + \dots + x_n^2) = 2^n. \quad (11)
Now let λ>0\lambda > 0. There cannot be more than 2n2/λ22^{n-2}/\lambda^2 terms ΔA2\Delta_A^2 whose value greater than or equal to 4λ24\lambda^2. If this were not the case, then the sum of these terms would be greater than 2n2^n, so the sum in (11) would exceed 2n2^n. Hence, there can be at most 2n2/λ22^{n-2}/\lambda^2 sets AA such that SAλ|S_A| \ge \lambda. (Recall that ΔA=2SA\Delta_A = 2S_A.) Moreover, these sets can be arranged into complementary pairs because SA=S{1,,n}AS_A = -S_{\{1, \dots, n\} \setminus A}. In each of these pairs, exactly one of the two members is positive. Therefore there are at most 2n3/λ22^{n-3}/\lambda^2 sets AA with SAλS_A \ge \lambda.

For equality to hold, it must be the case that all positive values of ΔA2\Delta_A^2 are equal to 4λ24\lambda^2; otherwise we would again have a contradiction because the sum of all ΔA2\Delta_A^2 would exceed 2n2^n. In particular, all positive values of ΔA2\Delta_A^2 must be the same. Thus, all positive values of xAx_A must be the same. This will be the case only if at most one of the xix_i is positive and at most one of the xix_i 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 xk=2/2x_k = \sqrt{2}/2 for some kk, xj=2/2x_j = -\sqrt{2}/2 for some jkj \neq k, and xi=0x_i = 0 for ij,ki \neq j, k. Then the assumption that every positive ΔA2=4λ2\Delta_A^2 = 4\lambda^2 yields λ=2/2\lambda = \sqrt{2}/2.

Conversely, with the xix_i and λ\lambda as described, we have exactly 2n2=2n3/λ22^{n-2} = 2^{n-3}/\lambda^2 sets AA such that xAλx_A \ge \lambda: namely, the sets AA that contain the 2/2\sqrt{2}/2 term and do not contain the 2/2-\sqrt{2}/2 term. Thus, this is indeed the equality case.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.