wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> How Many Triangles
        
(Message started by: william wu on Feb 16^th, 2003, 3:55pm)

Title: How Many Triangles
Post by william wu on Feb 16^th, 2003, 3:55pm

Source: Macedonia Mathematics Olympiad, 1997

Given some integer n, how many non-congruent triangles are there whose sides are all of integral length and less than or equal to 2n?

Title: Re: How Many Triangles
Post by Eigenray on Apr 25^th, 2003, 12:16am

We count the number of ordered triples (x,y,z) such that:
1<= x <= y <= z <= 2n
x + y > z <-> x > z-y <-> x >= z-y+1
This is "simply":
sum_{z=1}^{2n} sum_{y=1}^{z} sum_{x=z-y+1}^{y} 1
Note that the last sum vanishes unless y >= z-y+1, i.e., y>=(z+1)/2.
Thus we get:
F(n) = sum_{z=1}^{2n} sum_{y=ceil[(z+1)/2]}^{z} (2y-z)
= sum_{z=1}^{2n} G(z)
If z=2k is even,
G(z)=G(2k)=sum_{y=k+1}^{2k} (2y-2k)
= sum_{m=1}^{k} 2m
= k(k+1)
If z=2k-1 is odd,
G(z)=G(2k-1)=sum_{y=k}^{2k-1} (2y-2k+1)
= sum_{y=k+1}^{2k} (2y-2k-1)
= G(2k) - k

Then F(n) = sum_{k=1}^{n} G(2k-1) + G(2k)
= sum_{k=1}^{n} 2k(k+1) - k
= sum_{k=1}^{n} 2/3*[(k+1)^3-k^3 - 1] - n(n+1)/2
= 2/3*[(n+1)^3-1 - n] - n(n+1)/2
= ( 4n^3 + 9n^2 + 5n ) /6
= n(4n^2+9n+5)/6
= n(4n+5)(n+1)/6