Skip to main content
3 of 3
fixed mistake about sorting
Selim
  • 489
  • 1
  • 6
  • 11

Write $x_i = a_i/b_i$, $y_i= t_i b_i$. Your inequality then reduces to the question of if there is some $C$ such that sometimes

$$ C \sum_i x_i y_i \le \sum_i x_i \cdot \sum_i y_i, $$ and if so, under what conditions.

One answer to this question goes by the name of Chebyshev's inequality in math olympiad circles; it's sometimes called Chebyshev's order inequality or Chebyshev's sum inequality to distinguish it from the (apparently unrelated?) result in probability theory. It can be found in Hardy–Littlewood–Pólya, Steele's book The Cauchy–Schwarz Masterclass, and various places on the internet.

In brief, $C=n$, and the condition is that the $x_i$ and $y_i$ have to be oppositely sorted (meaning that we can permute the indices such that $x_1 \le \dotsb \le x_n$ and $y_1 \ge \dotsb \ge y_n$). The $y_i$ don't have to be non-negative, but the sorting condition is crucial: if they are similarly sorted, then the inequality flips its direction!

Selim
  • 489
  • 1
  • 6
  • 11