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 »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: How Many Triangles  (Read 721 times)
william wu

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

 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 »

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