Mathematical Food for Thought

  
 
google
yahoo
bing
 

  • About

    Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
  
Square Differences. Topic: Inequalities. Level: Olympiad. January 21st, 2006

Problem: (1975 IMO – #1) We consider two sequences of real numbers x_{1} \geq x_{2} \geq \ldots \geq x_{n} and \ y_{1} \geq y_{2} \geq \ldots \geq y_{n}. Let z_{1}, z_{2}, \ldots, z_{n} be a permutation of the numbers y_{1}, y_{2}, \ldots, y_{n}. Prove that \displaystyle \sum \limits_{i=1}^{n} ( x_{i} -\ y_{i} )^{2} \leq \sum \limits_{i=1}^{n} ( x_{i} – z_{i})^{2}.

Solution: Expanding both sides, we see that

\displaystyle \sum x_i^2 and \displaystyle \sum y_i^2 = \sum z_i^2 appear on both sides, so we can cancel them out, leaving

\displaystyle -2 \sum x_iy_i \le -2 \sum x_iz_i \Rightarrow \sum x_iy_i \ge \sum x_iz_i which is a direct result of the Rearrangement Inequality (easily extended to all reals). QED.

——————–

Comment: Well, I can’t say this is the toughest IMO problem ever, but it does teach a few good lessons. One might be inclined to keep the squared differences there because they do look a bit nicer than after expansion. But getting a little messy can sometimes produce exactly the result you want, as it does here. Knowing the Rearrangement Inequality basically gives you the first ideas of an approach which is easy to finish.

——————–

Practice Problem: Extend the Rearrangement Inequality to all reals (i.e. show that the proof holds even when there are negative numbers).

Posted in Inequalities, Olympiad || No Comments »

Leave a Reply

You must be logged in to post a comment.
Google

 

  
 
free web counters
Etronics