wu :: forums « wu :: forums - How Many Triangles » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 2:58pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  putnam exam (pure math) (Moderators: Grimbal, Icarus, SMQ, Eigenray, towr, william wu)  How Many Triangles « Previous topic | Next topic » Author Topic: How Many Triangles  (Read 721 times)
william wu       Gender: Posts: 1291 How Many Triangles   « on: Feb 16th, 2003, 3:55pm » Quote Modify

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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »