wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> A condition for sides of triangle
        
(Message started by: Aryabhatta on May 16^th, 2007, 12:12am)

Title: A condition for sides of triangle
Post by Aryabhatta on May 16^th, 2007, 12:12am

A surprising result, which appeared as a problem in a recent IMO.

If n >= 3 is a positive integer and t₁, t₂, ..., t_n are positive reals such that

[ (t₁ + t₂ + ... + t_n) (1/t₁ + 1/t₂ + ... + 1/t_n) ] = n²

Then any (t_i, t_j, t_k) form the sides of some triangle. (i,j,k are distinct)

([x] = integral part of x.)

Title: Re: A condition for sides of triangle
Post by Aryabhatta on May 16^th, 2007, 10:10am

In fact we can show the following too I think:

a) if n >= 25, then the t_i,j,k triplets not only form the sides of a triangle, they form the sides of an acute angled triangle.

b) Given an e > 0, there is some N (dependent on e) such that if n >= N and the t_i satisfy the conditions of the problem, then 1 + e > t_i/t_j for all i,j.

i.e if {t₁, t₂, ..., t_n,...} is a sequence of t_is which satisfy the conditions of the above problem for every n > M (pick any M) then they must all be equal.

Title: Re: A condition for sides of triangle
Post by Aryabhatta on May 22^nd, 2007, 1:32pm

Maybe this should be moved to Putnam the section...

Title: Re: A condition for sides of triangle
Post by Eigenray on May 24^th, 2007, 7:50am

Replace n by n+2, and suppose the numbers are

a < t₁ < t₂ < ... < t_n < b
We may scale so that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif t_i = 1. Then by AM-GM, we have

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gift_i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif n, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif1/t_i http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif n
Thus

(a+b+n)(1/a+1/b+n) < (n+2)² + 1,
(a/b+b/a) + n(a+1/a+b+1/b) < 4n+3,
a+1/a + b+1/b < 4 + 1/n,
since a/b+b/a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 2. For n large, a+1/a and b+1/b must be close to 2, which means a and b must be close to 1, so their ratio is close to 1. This shows (b). For (a), suppose

a+1/a + b+1/b < c = 4 + 1/n.

Writing b=ra, we have

a(1+r) + 1/a (1+1/r) < c
Since a is real, this requires that the discriminant

c² - 4(1+r)(1+1/r) > 0,
and solving for r we have

r < c²/8 - 1 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{(c^2/8 - 1)² - 1}
= 1+1/n+1/(8n²) + (4n+1)/(8n²)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{8n+1}
= 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{2/n}+O(1/n).

In particular, if n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 17 (or 19, in the original problem), then the largest ratio r=b/a < 1.409 < http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2, so the smallest ratio is > 1/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2. So for any three of our numbers a,b,c, we have (a/c)² + (b/c)² > 1, which means that all triangles are acute.

Note that the single largest ratio is obtained when all but the smallest and largest numbers are equal, so this doesn't give the best bound for showing all triangles are acute, which involves the sum of the squares of two different ratios. So it may be true for some smaller n as well.

Title: Re: A condition for sides of triangle
Post by Eigenray on May 24^th, 2007, 8:04am

Oh, and the original problem (which is very nice): Isolate three of the numbers a,b,c. We need to show a+b>c, or that a/c + b/c > 1. So write

(a+b+c+ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif^' t_i)(1/a+1/b+1/c+ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif^' 1/t_i) = n + a/c+c/a+b/c+c/b + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif^' (t_i/t_j+t_j/t_i),

where the final http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif^' is over the C(n,2)-2 pairs other than {a,c} and {b,c}. Each term in the sum is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 2, so we have

a/c+c/a+b/c+c/b + n+2(n(n-1)/2-2) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif t_i)(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif 1/t_i) < n²+1.

Letting u=a/c, v=b/c, we have

u+1/u + v+1/v < 5,

and we want to show s=u+v>1. By AM-HM,

u+v + 2[(1/u+1/v)/2] http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif u+v + 4/(u+v),

so we have

s + 4/s < 5,

and therefore s>1, as desired.

Title: Re: A condition for sides of triangle
Post by Aryabhatta on May 24^th, 2007, 1:41pm

Well done Eigenray!

Here is the proof for the IMO problem I had in mind:

We are only dealing with positive reals.

Lemma:
if
(a₁ + ...+ a_n)(1/a₁ + ...+ 1/a_n) >= S²

then for any real a > 0

(a₁ + ...+ a_n+ a)(1/a₁ + ...+ 1/a_n+ 1/a) >= (S+1)²

Proof: Put K = Sigma a_i and K' = Sigma 1/a_i.

Now we have (K+a)(K'+1/a) = KK' + 1 + K/a + aK'
Now K/a + aK' >= 2sqrt(KK') by AM >= GM.
Since KK' >= S² we are done.

Thus if there are some 3 numbers say t₁, t₂, t₃ for which we have that

(t₁ + t₂ + t₃)(1/t₁ + 1/t₂ + 1/t₃) >= 10 = 3² + 1

then we have by induction and using above lemma that:

(t₁ + t₂ + .. + t_n)(1/t₁ + 1/t₂ + ... + 1/t_n) >= n² + 1

Now if t₁, t₂, t₃ do not form the sides of a triangle, we can show that

(t₁ + t₂ + t₃)(1/t₁ + 1/t₂ + 1/t₃) >= 10

(Will update this post with the proof of the last fact later)

Title: Re: A condition for sides of triangle
Post by Eigenray on May 24^th, 2007, 2:13pm

I like that your proof gives a slightly stronger result.

What argument do you have for the acute triangle when n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 25? I have something simpler (bounding a and b near 1 independently) but it only works for n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 36.

Title: Re: A condition for sides of triangle
Post by Aryabhatta on May 24^th, 2007, 7:21pm

I got n >=25 using the following:

say x,y,z (among the t_is) are not the sides of an acute angled triangle, and say we find a c such that

(x+y+z)(1/x+1/y+1/z) >= (3+c)²

then by using the above lemma, we find that

(t₁ + ... + t_n)(1/t₁ + ... + 1/t_n) >= (n+c)²

Now if c is such that for n >=25, (n+c)² >= n²+1 then we are done.

For 3 numbers we can take them as 1, x and y where x >=1 and y² >= x² + 1

We can show that (1+x+y)(1+1/x+1/y) is a increasing function of y (if y is the largest)

So we consider the case when y = sqrt(x²+1)

(1 + x + y)(1 + 1/x + 1/y) = 3 + (x+1/x) + (x/y + y/x) + (y + 1/y) >= 7 + (y + 1/y)

Now y = sqrt(x²+1) >= sqrt(2)
We have that y + 1/y is increasing for y >= 1 so y + 1/y >= 1/sqrt(2) + sqrt(2)
So we have that
(1 + x + y)(1 + 1/x + 1/y) >= 7 + 3/sqrt(2) = 9 + (3-2sqrt(2))/sqrt(2)

Thus if (3+c)² = 9 + (3-2sqrt(2))/sqrt(2)

then (n+c)² >= n² + 1 for n >= 25.

This is a crude (and not very simple) estimate and i think we can certainly do better.

Title: Re: A condition for sides of triangle
Post by Aryabhatta on May 25^th, 2007, 9:43am

I just realised, we can actually give a best estimate for the acute angled triangle problem!

We can show that:

i) If n >= 13, then the triangles must all be acute.

ii) if n < 13, we can find t_i such that there is at least one right triangle.

Here is an attempt to "prove" (i)

In the lemma described above,
if
(a₁ + ...+ a_n)(1/a₁ + ...+ 1/a_n) = S²

then for any real a > 0

(a₁ + ...+ a_n+ a)(1/a₁ + ...+ 1/a_n+ 1/a) >= (S+1)²

In fact equality occurs if a = sqrt(K/K') (for definition of K and K' see proof of Lemma)

Now suppose (wlog) 1,x,y among the t_i do not form an acute triangle where 1 <= x and y >= sqrt(x² + 1)

Then consider
(1+x+y)(1+1/x+1/y) which is increasing in y.

So it is enough to consider the case when y = sqrt(x²+1)

expanding we get

1 + x + 1/x + y + 1/y + x/y + y/x

putting x = tan(z) where z is in [pi/4, pi/2) we can show that this is increasing in z (and hence in x) (i just used an online plotter, didn't try proving it, should be straight forward i suppose)

Thus min occurs when x= 1 and y = sqrt(2)

i.e
(1+x+y)(1+1/x+1/y) >= 5 + 3sqrt(2) = (3+c)² say.

For this c, we see that (I used a calculator) 13 > (1-c²)/2c > 12

Now (n+c)^² >= n² + 1
iff n >= (1-c²)/2c > 12

I.e if n >= 13 then the triangles have to be acute.

for part (ii)

if n <= 12,

We start out with a₁ = 1, a₂ = 1,a₃ = sqrt(2)
we keep adding new numbers a_i for which the equality in the lemma holds (a_i = sqrt(K/K'))

For these numbers we have the n²+1 > (n+c)² = (1 + 1 + sqrt(2) + a₄ + .. + a_n)(1+ 1+ 1/sqrt(2) + ... + 1/a_n) and we have a right triangle by using 1,1 and sqrt(2)