Author |
Topic: How Many Triangles (Read 736 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
How Many Triangles
« on: Feb 16th, 2003, 3:55pm » |
 Quote  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:
Posts: 1948
|
|
Re: How Many Triangles
« Reply #1 on: Apr 25th, 2003, 12:16am » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print