Big with big, small with small
Tonight's idea
Take two prices \(a \le b\) and two quantities \(x \le y\). Pair each price with a quantity, multiply, and add. Matching small with small gives \(ax + by\). Crossing them gives \(ay + bx\).
Two-pair swap. If \(a \le b\) and \(x \le y\), then \(ax + by \ge ay + bx\).
Proof. Subtract: \((ax + by) - (ay + bx) = (b - a)(y - x)\). Neither bracket is negative, so neither is the product.
Now take longer lists. Let \(a_1 \le a_2 \le \dots \le a_n\), and pair them with \(b\)'s in any order. If the largest \(b\) is not with \(a_n\), swap it with the \(b\) that is. Those two pairs go from crossed to matched, so the sum does not fall. Leave that pair alone and do the same for the next largest \(b\), and so on. At the end the \(b\)'s are in increasing order too, and the sum never fell.
Rearrangement inequality. The sum \(a_1b_1 + \dots + a_nb_n\) is largest when both lists are sorted the same way. It is smallest when they are sorted opposite ways (apply this to the list of \(-b\)'s, which reverses both their order and the inequality).
Watch one: \(a^2 + b^2 + c^2 \ge ab + bc + ca\)
First with numbers. Pair \((1, 3, 4)\) with \(2, 5, 6\) in all six orders. The sums are 41, 40, 35, 32, 31 and 29. The largest is \(1 \cdot 2 + 3 \cdot 5 + 4 \cdot 6 = 41\), sorted alike. The smallest is \(1 \cdot 6 + 3 \cdot 5 + 4 \cdot 2 = 29\), sorted opposite.
Now with letters. Take any real numbers \(a, b, c\) and use the list \((a, b, c)\) twice. A list is sorted the same way as itself, so pairing each number with itself gives the largest sum, \(a \cdot a + b \cdot b + c \cdot c\). Any other pairing is no bigger. Slide the second copy round one place, to \((b, c, a)\):
\[a^2 + b^2 + c^2 \ \ge\ ab + bc + ca.\]
No algebra, only the observation that one pairing is the sorted one.
Your turn
- Three piles hold 2, 5 and 9 coins. One pile must be all 10-cent coins, one all 20-cent and one all 50-cent. What is the most money the piles can hold? The least?
- Use the list \((a, b)\) twice to prove \(a^2 + b^2 \ge 2ab\) for any real numbers. Deduce that \(\dfrac{x}{y} + \dfrac{y}{x} \ge 2\) for positive \(x\) and \(y\).
- For positive \(a, b, c\), prove \(a^3 + b^3 + c^3 \ge a^2b + b^2c + c^2a\). Say which two lists you are pairing, and why they are sorted the same way.
- Four customers need 2, 4, 5 and 9 minutes at a single till. Each person's wait runs until their own service ends. If the service times in order are \(t_1, t_2, t_3, t_4\), explain why the total wait is \(4t_1 + 3t_2 + 2t_3 + t_4\). Which order makes it smallest? Find the smallest and largest totals.
Stretch: Nesbitt's inequality
For positive \(a, b, c\), prove \(\dfrac{a}{b+c} + \dfrac{b}{c+a} + \dfrac{c}{a+b} \ge \dfrac32\). Hint: the lists \((a, b, c)\) and \(\left(\tfrac{1}{b+c}, \tfrac{1}{c+a}, \tfrac{1}{a+b}\right)\) are sorted the same way. Write down the two slid pairings and add them.
Answers
- Most: big with big, \(2 \times 10 + 5 \times 20 + 9 \times 50 = 570\) cents. Least: opposite order, \(2 \times 50 + 5 \times 20 + 9 \times 10 = 290\) cents.
- Pairing \((a, b)\) with itself is the sorted pairing, \(a^2 + b^2\). The other pairing is \(ab + ba = 2ab\). So \(a^2 + b^2 \ge 2ab\). Put \(a = x\), \(b = y\) and divide by \(xy\), which is positive: \(\tfrac{x}{y} + \tfrac{y}{x} \ge 2\).
- Pair \((a^2, b^2, c^2)\) with \((a, b, c)\). For positive numbers a bigger number has a bigger square, so the two lists are sorted the same way. The matched pairing is \(a^3 + b^3 + c^3\). Sliding the second list to \((b, c, a)\) gives \(a^2b + b^2c + c^2a\), which is no bigger.
- The first service time is waited through by all four people, the second by three, the third by two and the last by one. The multipliers \(4, 3, 2, 1\) are fixed, so the total is smallest when the times are sorted the opposite way: shortest first. Smallest: \(4 \cdot 2 + 3 \cdot 4 + 2 \cdot 5 + 1 \cdot 9 = 39\) minutes. Largest (longest first): \(4 \cdot 9 + 3 \cdot 5 + 2 \cdot 4 + 1 \cdot 2 = 61\) minutes.
Stretch. The expression does not change if the letters are renamed, so take \(a \le b \le c\). Then \(b + c \ge c + a \ge a + b\), so \(\tfrac{1}{b+c} \le \tfrac{1}{c+a} \le \tfrac{1}{a+b}\): sorted the same way as \((a, b, c)\). Call the matched sum \(S\). The two slid pairings are no bigger: \(S \ge \tfrac{b}{b+c} + \tfrac{c}{c+a} + \tfrac{a}{a+b}\) and \(S \ge \tfrac{c}{b+c} + \tfrac{a}{c+a} + \tfrac{b}{a+b}\). Add them: \(2S \ge \tfrac{b+c}{b+c} + \tfrac{c+a}{c+a} + \tfrac{a+b}{a+b} = 3\). So \(S \ge \tfrac32\). The three inequalities were \(a^2 + b^2 \ge 2ab\), \(a^2 + b^2 + c^2 \ge ab + bc + ca\), and Nesbitt's.