x1, x2, ... , xn, and y1, y2, ... , yn are non-negative reals. Show that ∑ min(xixj, yiyj) ≤ ∑ min(xiyj, xjyi), where each sum is taken over all n2 pairs (i, j).
Solution
Let f(x1, y1, x2, y2, ... , xn, yn) = S ( min(xiyj, xjyi) - min(xixj, yiyj) ). So we have to show that f(x1, y1, ... , xn, yn) ≥ 0. We use induction on n. There is nothing to prove for n = 1. Suppose the result is true for all positive integers < n.
If any xi or yi is zero, or if any xi = yi, then the result follows immediately from that for n-1. Suppose x1/y1 = x2/y2. We claim that f(x1, ... , yn) = f(x1+x2, y1+y2, x3, y3, ... , xn, yn). Note that the rhs has one less pair of terms. For convenience we write x1 = k y1, so x2 = k y2. The sum of the (1, i) and (2, i) terms on the lhs is min( x1yi, y1xi) + min( x2yi, y2xi) - min( x1xi, y1yi) - min( x2xi, y2yi) = (y1 + y2) min(kyi, xi) - (y1 + y2) min(kxi, yi). The corresponding (1+2, i) term on the rhs is min( (x1+x2)yi, (y1+y2)xi) - min( (x1+x2)xi, (y1+y2)yi) = (y1+y2) min(kyi, xi) - (y1+y2) min(kxi, yi), which is the same. Similarly for the (i, 1) + (i, 2) versus (i, 1+2) terms. The (i, j) terms (with i, j > 2) are obviously unchanged. So we just have to consider the various 1, 2 terms. On the lhs there are four of them: the (1, 1), (1, 2) = (2, 1) and the (2, 2) terms. Their sum is x1y1 - min(x12, y12) + x2y2 - min(x22, y22) + 2min(x1y2, x2y1) - 2min(x1x2, y1y2) = ky12 - y12min(k2, 1) + ky22 - y22min(k2, 1) + 2ky1y2 - 2y1y2min(1,k2) = (y1+y2)2(k - min(1,k2) ). On the rhs there is just the one term (x1+x2)(y1+y2) - min( (x1+x2)2, (y1+y2)2) = k(y1+y2)2 - (y1+y2)2min(k2, 1), which is the same. So we have established the claim. Thus if we have any distinct i, j such that xi/yi = xj/yj, then the result for n follows from that for n-1.
We now show that the same is true if we have xi/yi = yj/xj. Assume for convenience that x1/y1 = y2/x2. We can also assume without loss of generality that x1 ≤ y2. So we can take x2 = ky1, y2 = k x1 with k ≥ 1. Then we claim that f(x1, ... , yn) = f(x2 - y1, y2 - x1, x3, y3, ... , xn, yn). Again, the rhs has one less pair of terms than the lhs. On the lhs the sum of the (1, i) and (2, i) terms on the lhs is min( x1yi, y1xi) + min( x2yi, y2xi) - min( x1xi, y1yi) - min( x2xi, y2yi) = (k-1) min(x1xi, y1yi) - (k-1) min(x1yi, y1xi) . The corresponding (1+2, i) term on the rhs is min( (x2-y1)yi, (y2-x1)xi) - min( (x2-y1)xi, (y2-x1)yi) = (k-1) min(y1yi, x1xi) - (k-1) min(y1xi, x1yi), which is the same. Similarly, the 1, 2 terms on the lhs are x1y1 - min(x12, y12) + x2y2 - min(x22, y22) + 2min(x1y2, x2y1) - 2min(x1x2, y1y2) = x1y1 - min(x12, y12) + k2x1y1 - k2min(x12, y12) + 2k min(x12, y12) - 2kx1y1 = (1 - k)2x1y1 - (1 - k)2min(x12, y12). On the rhs we have (x2 - y1)(y2 - x1) - min( (x2 - y1)2, (y2 - x1)2) = (k - 1)2x1y1 - (k - 1)2min(y12, x12), which is the same. Again the terms not involving 1 or 2 are the same on both sides. So we have shown that if we have any distinct i, j such that xi/yi = yj/xj then the result for n follows from that for n-1.
Put ri = max(xi/yi, yi/xi). Reordering the pairs, if necessary, we can take 1 ≤ r1 ≤ r2 ≤ ... ≤ rn. Now let us consider all the xi, yi as fixed except y1. For convenience, let us write t = y1. We have 1 ≤ r1 ≤ r2, so t can take any value in the interval [x1, x1r2] or any value in the interval [x1/r2, x1]. We examine f on each of these intervals. Since only t is varying, the only terms in f which vary are the (1, 1), (1, i) and (i, 1) terms. Writing their sum as g(t), we have g(t) = x1t - min(x12, t2) + 2 ∑ min(x1yi, t xi) - 2 ∑ min(x1xi, t yi). Now if xi ≥ yi, then xi/yi = ri ≥ r2 ≥ t/x1, so x1xi ≥ t yi. Also t xi ≥ x1xi ≥ x1yi, so min(x1yi, t xi) = x1yi, and min(x1xi, t yi) = t yi. So if we put zi = - yi, then these two terms in g(t) give 2(t - x1) zi. Similarly, if xi < yi, then x1yi ≥ t xi and t yi ≥ x1xi, so if we put zi = xi, then the two terms in g(t) still give 2(t - x1) zi. Thus g(t) = x1t - x12 + 2(t - x1) ∑ zi, which is linear in t. But a linear function takes its minimum value in an interval at one of the endpoints, so the minimum value of g(t) (and hence of f as t varies) must occur at t = x1 or x1r2. But then we have r1 = 1 or r2 and in both those cases we have established that the value of f equals the value of f for n-1 pairs and is therefore non-negative.
Now suppose t is in the other interval [x1/r2, x1]. Again, we put g(t) equal to the sum of the variable terms. So g(t) = x1t - min(x12, t2) + 2 ∑ min(x1yi, t xi) - 2 ∑ min(x1xi, t yi). Again, we consider separately the case xi ≥ yi which gives a pair of terms with sum 2(x1 - t)zi if we put zi = yi, whilst if xi < yi, then the pair of terms has the sum 2(x1 - t)zi if we put zi = -xi. So we get g(t) = x1t - t2 + 2(x1 - t) ∑ zi. This time we have a quadratic. But the leading term - t2 has a negative coefficient, so g(t) has a single maximum as t varies over all real values. Thus it is again true that the minimum value over the interval [x1/r2, x1] must occur at one of the endpoints. So again the minimum value of f as t varies over the allowed range is at r1 = r2 or 1 and is hence non-negative by induction.
So the induction is complete and the result established.
Comment. No one made any headway with this in the USAMO exam. As an olympiad problem, it is exceptionally (and unreasonably) difficult.
© John Scholes
jscholes@kalva.demon.co.uk
26 Aug 2002