Maths Olympiad Prep

Track / Stage 6 / 399 of 400 #1399 of 1964

Problem 1399

National olympiad, first round
Combinatorics Difficulty 7.0 Prove it

Let ω1,ω2,...,ωk\omega_1,\omega_2, . . . ,\omega_k be distinct real numbers with a nonzero sum. Prove that there exist integers n1,n2,...,nkn_1, n_2, . . . , n_k such that i=1kniωi>0\sum_{i=1}^k n_i\omega_i>0, and for any non-identical permutation π\pi of {1,2,,k}\{1, 2,\dots, k\} we have
i=1kniωπ(i)<0.\sum_{i=1}^k n_i\omega_{\pi(i)}<0.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. **Assume the ordering of ωi\omega_i**: Without loss of generality, let ω1>ω2>>ωk\omega_1 > \omega_2 > \ldots > \omega_k. Define the sum S=ω1+ω2++ωkS = \omega_1 + \omega_2 + \ldots + \omega_k. Since the ωi\omega_i are distinct and their sum is nonzero, S0S \neq 0.

2. Identify the greatest and second greatest sums: Consider sums of the form 2ωπ(1)+ωπ(2)++ωπ(k)2\omega_{\pi(1)} + \omega_{\pi(2)} + \ldots + \omega_{\pi(k)} for permutations π\pi of {1,2,,k}\{1, 2, \ldots, k\}. The greatest sum is 2ω1+ω2++ωk2\omega_1 + \omega_2 + \ldots + \omega_k, and the second greatest sum is ω1+2ω2+ω3++ωk\omega_1 + 2\omega_2 + \omega_3 + \ldots + \omega_k.

3. Use the density of rationals: Because the rationals are dense in the reals, we can find a rational number ϵ=ab\epsilon = \frac{a}{b} with b>0b > 0 such that:
ω1+2ω2++ωk+Sϵ<0<2ω1+ω2++ωk+Sϵ \omega_1 + 2\omega_2 + \ldots + \omega_k + S\epsilon < 0 < 2\omega_1 + \omega_2 + \ldots + \omega_k + S\epsilon

4. Formulate the inequalities: We can rewrite the inequalities as:
(2+ϵ)ω1+(1+ϵ)ω2++(1+ϵ)ωk>0 (2 + \epsilon)\omega_1 + (1 + \epsilon)\omega_2 + \ldots + (1 + \epsilon)\omega_k > 0
and
(1+ϵ)ω1+(2+ϵ)ω2+(1+ϵ)ω3++(1+ϵ)ωk<0 (1 + \epsilon)\omega_1 + (2 + \epsilon)\omega_2 + (1 + \epsilon)\omega_3 + \ldots + (1 + \epsilon)\omega_k < 0

5. **Generalize for any permutation π\pi**: For any non-identical permutation π\pi of {1,2,,k}\{1, 2, \ldots, k\}, we have:
(2+ϵ)ωπ(1)+(1+ϵ)ωπ(2)++(1+ϵ)ωπ(k)<0 (2 + \epsilon)\omega_{\pi(1)} + (1 + \epsilon)\omega_{\pi(2)} + \ldots + (1 + \epsilon)\omega_{\pi(k)} < 0

6. **Choose appropriate integers nin_i**: Let n1=b(2+ϵ)=2b+an_1 = b(2 + \epsilon) = 2b + a and ni=b(1+ϵ)=b+an_i = b(1 + \epsilon) = b + a for 2ik2 \leq i \leq k. Then:
i=1kniωi=(2b+a)ω1+(b+a)ω2++(b+a)ωk \sum_{i=1}^k n_i \omega_i = (2b + a)\omega_1 + (b + a)\omega_2 + \ldots + (b + a)\omega_k
and for any non-identical permutation π\pi:
i=1kniωπ(i)=(b+a)ωπ(1)+(2b+a)ωπ(2)+(b+a)ωπ(3)++(b+a)ωπ(k) \sum_{i=1}^k n_i \omega_{\pi(i)} = (b + a)\omega_{\pi(1)} + (2b + a)\omega_{\pi(2)} + (b + a)\omega_{\pi(3)} + \ldots + (b + a)\omega_{\pi(k)}

7. Verify the inequalities: By construction, the chosen nin_i satisfy:
i=1kniωi>0 \sum_{i=1}^k n_i \omega_i > 0
and for any non-identical permutation π\pi:
i=1kniωπ(i)<0 \sum_{i=1}^k n_i \omega_{\pi(i)} < 0

Thus, the integers n1,n2,,nkn_1, n_2, \ldots, n_k exist and satisfy the required conditions.

\blacksquare

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.