wu :: forums
wu :: forums - How Many Triangles

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 2:58pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Grimbal, Icarus, SMQ, Eigenray, towr, william wu)
   How Many Triangles
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: How Many Triangles  (Read 721 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
How Many Triangles  
« on: Feb 16th, 2003, 3:55pm »
Quote Quote Modify Modify

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?
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: How Many Triangles  
« Reply #1 on: Apr 25th, 2003, 12:16am »
Quote Quote Modify Modify

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
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board