USA TST 2007 Day 1 P2

For discussing Olympiad Level Algebra (and Inequality) problems
User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am
USA TST 2007 Day 1 P2

Unread post by Thanic Nur Samin » Sun Nov 20, 2016 11:51 pm

Let $n$ be a positive integer and let $a_1 \le a_2 \le \dots \le a_n$ and $b_1 \le b_2 \le \dots \le b_n$ be two nondecreasing sequences of real numbers such that
\[ a_1 + \dots + a_i \le b_1 + \dots + b_i \text{ for every } i = 1, \dots, n \]
and
\[ a_1 + \dots + a_n = b_1 + \dots + b_n. \]
Suppose that for every real number $m$, the number of pairs $(i,j)$ with $a_i-a_j=m$ equals the numbers of pairs $(k,\ell)$ with $b_k-b_\ell = m$. Prove that $a_i = b_i$ for $i=1,\dots,n$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: USA TST 2007 Day 1 P2

Unread post by Thanic Nur Samin » Mon Nov 21, 2016 12:02 am

Solution:
Take the sum of all differences for both sequences, since each difference in one sequence must have a corresponding equal difference in the other, the quantity would be same. Multiply both sides with $(-1)$. Add $(n-1)(a_1 + \dots + a_n) = (n-1)(b_1 + \dots + b_n)$ to both sides and divide by 2. We then get :
\[(n-1)a_1+(n-2)a_2+\dots 2a_{n-2}+a_{n-1}=(n-1)b_1+(n-2)b_2+\dots 2b_{n-2}+b_{n-1}\]
However, the summing the following inequality while $i$ runs from $1$ to $n-1$:
\[a_1 + \dots + a_i \le b_1 + \dots + b_i\]
We get:
\[(n-1)a_1+(n-2)a_2+\dots 2a_{n-2}+a_{n-1}\le (n-1)b_1+(n-2)b_2+\dots 2b_{n-2}+b_{n-1}\]
Since the equality case occurs, the equality case must occur in all the inequalities. From this, the desired result follows.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply