Let $ a_1$, $ a_2$, ..., $ a_n$ and $ b_1$, $ b_2$, ..., $ b_n$ be $ 2 \cdot n$ real numbers. Prove that the following two statements are equivalent: i) For any $ n$ real numbers $ x_1$, $ x_2$, ..., $ x_n$ satisfying $ x_1 \leq x_2 \leq \ldots \leq x_ n$, we have $ \sum^{n}_{k = 1} a_k \cdot x_k \leq \sum^{n}_{k = 1} b_k \cdot x_k,$ ii) We have $ \sum^{s}_{k = 1} a_k \leq \sum^{s}_{k = 1} b_k$ for every $ s\in\left\{1,2,...,n-1\right\}$ and $ \sum^{n}_{k = 1} a_k = \sum^{n}_{k = 1} b_k$.
Problem
Source: China TST 1986, problem 2
Tags: inequalities, function, vector, algebra unsolved, algebra
16.05.2005 21:43
The intention must be that (i) is true for all possible increasing n-tuples $ x$, otherwise the problem is false. Also, the inequality in (ii) must go the opposite way, as follows from the proof below. Here is the corrected version: [Moderator edit: I have corrected Orl's original post above according to this. $ -$ Darij] This problem is very interesting, because (ii) is the condition for $ b$ to majorize $ a$, but without the usual condition that $ a$, $ b$ are ordered. So it looks like a majorization condition for the class of increasing functions in place of convex ones. Therefore, there should be several more equivalent conditions such as (iii) Sequence $ b$ can be obtained from $ a$ by a series of transformations of the following type: given indices $ i < j$ and a positive real number $ p \geq 0$, change $ a_i \to a_i - p$ and $ a_j \to a_j + p$. Question : what is the analogue of the convex majorization criterion using double stochastic matrices (row and column sums = 1, Birkhoff polytope)? Anyway, the proof for the problem: Inequality (i) holds for all n-tuples $ x$ if and only if it holds for constant n-tuples $ (c,c,c,...,c)$ and all n-tuples of the form $ (0,0,...,1,1,1,...)$. This is because any increasing sequence $ x$ can be written as a sum (with non-negative coefficients) of such vectors. (i) for constant vectors is the condition $ \Sigma a_i = \Sigma b_i$. (i) for the vector with $ x_i = 0$ for $ i < k$ and $ x_i = 1$ for $ i \geq k$ is the condition $ \sum^{n}_{i = k} a_i \leq \sum^{n}_{i = k} b_i$. That's all.
05.07.2006 15:03
Here is an easy way to help solve inequaility (ii). If we let S(k)= (a1+a2+^^^+ak)-(b1+b2+^^^bk). We will get a(k+1)-b(k+1)=S(k+1)-S(k) Noticing that S(m) is greater than or equal to 0. for every positive integer m such that 1≤m≤n-1, and S(n)=0 we can get the proof easily by computing the difference between the two sides of the inequality (ii).