Skip to main content
fixed mistake about sorting
Source Link
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 similarlyoppositely sorted (meaning that if we re-index them simultaneouslycan permute the indices such that $x_1 \le \dotsb \le x_n$, then and $y_1 \le \dotsb \le y_n$$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 oppositelysimilarly sorted, then the inequality flips its direction!

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 similarly sorted (meaning that if we re-index them simultaneously such that $x_1 \le \dotsb \le x_n$, then $y_1 \le \dotsb \le y_n$). The $y_i$ don't have to be non-negative, but the sorting condition is crucial: if they are oppositely sorted, then the inequality flips its direction!

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!

added the content of the references; added 1 characters in body; added 5 characters in body
Source Link
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 similarly sorted (meaning that if we re-index them simultaneously such that $x_1 \le \dotsb \le x_n$, then $y_1 \le \dotsb \le y_n$). The $y_i$ don't have to be non-negative, but the sorting condition is crucial: if they are oppositely sorted, then the inequality flips its direction!

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.

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 similarly sorted (meaning that if we re-index them simultaneously such that $x_1 \le \dotsb \le x_n$, then $y_1 \le \dotsb \le y_n$). The $y_i$ don't have to be non-negative, but the sorting condition is crucial: if they are oppositely sorted, then the inequality flips its direction!

Source Link
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.