wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> inequality & constraints: x_i x_j <= -1/n
        
(Message started by: william wu on Aug 23^rd, 2003, 10:05pm)

Title: inequality & constraints: x_i x_j <= -1/n
Post by william wu on Aug 23^rd, 2003, 10:05pm

Suppose you have n real numbers x₁, x₂, ... , x_n that satisfy the following two conditions:

[sum]_{i=1 to n} x_i = 0
[sum]_{i=1 to n} x_i[sup2] = 1

Prove that there exists integers i and j between 1 and n such that x_ix_j [le] -1/n.

Title: Re: inequality & constraints: x_i x_j <= -1/n
Post by Pietro K.C. on Sep 3^rd, 2003, 5:02pm

Hint 1:[hide]
Assume the opposite: that x_ix_j is greater than -1/n for all i, j.
[/hide]

Hint 2 (bigger):[hide]
Now you have constraints on the terms x_ix_j and x_i². In what kind of mathematical thing do these two often appear together?
[/hide]

Hint 3 (spoiler):[hide]
If the sum of the x_i is zero, so is the square of that sum. Work from there to derive a contradiction between that and your assumption that x_ix_j is greater than -1/n for all i, j.
[/hide]