Inequalities path · I08

Before this lesson: Sum of squares

Your goal: Prove why matching orders changes a sum of products.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Rearrangement inequality: the key idea

If a₁≤⋯≤aₙ and b₁≤⋯≤bₙ, pairing the lists in the same order maximises ∑aibπ(i)\sum a_{i}b_{\pi(i)}, while opposite order minimises it. The proof is a swap: for a≤A and b≤B, ab+AB−aB−Ab=(A−a)(B−b)≥0. Repeatedly remove inversions in any pairing. Real inputs of either sign are allowed because the ordered differences remain nonnegative. Strictly increasing lists make the maximal pairing unique; ties can give several equality pairings.

A worked example

Pair 1,3,5 with 2,4,8 to maximise the sum of products.

Same-order pairing gives 1·2+3·4+5·8=54. Opposite order gives the minimum 1·8+3·4+5·2=30. The swap argument proves these are extremal among all pairings.

Your turn: change one thing

Pair −2,1 with −3,4. Which pairing is larger?

Try this on paper before opening the explanation.

Compare your reasoning

Same order gives 6+4=10; crossed pairing gives −8−3=−11. The difference is 21=(1−(−2))(4−(−3)).

Pause and check

A trap to avoid: Forgetting to sort or carrying over an equality condition from distinct entries.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove the two-term rearrangement inequality for a≤A and b≤B.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Subtract the crossed sum from the same-order sum: ab+AB−aB−Ab=(A−a)(B−b). Both factors are nonnegative, so the difference is nonnegative. Equality holds when a=A or b=B.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. For two increasing lists, which pairing maximises the product sum?

Foundation

  1. Any order
  2. No pairing
  3. Same order
  4. Opposite order
Hint

Use the swap identity.

Answer and reasoning

Same order. Removing crossed pairs cannot decrease the sum.

2. Does rearrangement allow negative real inputs?

Foundation

  1. Only one negative
  2. Only integer inputs
  3. Yes, if each list is ordered
  4. No
Hint

The proof uses ordered differences.

Answer and reasoning

Yes, if each list is ordered. Ordered differences are nonnegative regardless of the signs of the original terms.

3. Maximum pairing sum for 1,3 and 2,5 is what?

Core

  1. 11
  2. 15
  3. 10
  4. 17
Hint

Pair increasing with increasing.

Answer and reasoning

17. 1·2+3·5=17.

4. Minimum pairing sum for 1,3 and 2,5 is what?

Core

  1. 10
  2. 11
  3. 17
  4. 15
Hint

Reverse one list.

Answer and reasoning

11. 1·5+3·2=11.

5. The gain from replacing aB+Ab by ab+AB equals what?

Stretch

  1. (A−a)(B−b)
  2. (A+a)(B+b)
  3. (A−a)(b−B)
  4. AB+ab
Hint

Factor the difference.

Answer and reasoning

(A−a)(B−b). ab+AB−aB−Ab=(A−a)(B−b).

6. Why can ties produce several maximal pairings?

Stretch

  1. Swapping equal entries changes nothing
  2. The inequality fails
  3. All pairings must tie
  4. Negative numbers are forbidden
Hint

A swap gain can be zero.

Answer and reasoning

Swapping equal entries changes nothing. When one ordered difference is zero, the swap leaves the sum unchanged.

7. For a≤A and b≤B, the product (A−a)(B−b) is what?

Foundation

  1. Always negative
  2. Always zero
  3. Undefined
  4. Nonnegative
Hint

Each factor is nonnegative.

Answer and reasoning

Nonnegative. The product of two nonnegative numbers is nonnegative.

8. Maximum pairing sum for 2,4 and 3,7?

Core

  1. 20
  2. 40
  3. 34
  4. 26
Hint

Pair equal ordering directions.

Answer and reasoning

34. 2·3+4·7=6+28=34.

9. How does the swap argument extend to n entries?

Stretch

  1. Assume the largest terms vanish
  2. Replace all entries by their means
  3. Repeatedly remove inverted pairings
  4. Check only one random pairing
Hint

Each swap improves or preserves the sum.

Answer and reasoning

Repeatedly remove inverted pairings. Sorting the pairing through nonnegative-gain swaps reaches the maximum same-order pairing.

Choose your next step

Continue to Chebyshev’s inequality. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.