fourier jr Posted June 20, 2004 Share Posted June 20, 2004 Let f(n) denote the maximum number of right triangles determined by n coplanar points. Prove f(n)/(n^2) --> infinity as n-->infinity and f(n)/(n^3) --> 0 as n-->infinity. Link to comment Share on other sites More sharing options...
bloodhound Posted June 24, 2004 Share Posted June 24, 2004 This is for the second part. Instead of finding f(n) explicitly we find g(n) for which [math]f(n) \le g(n)[/math] for all [math]n \ge 3[/math] Here [math]f,g:N \mapsto N[/math] and that [math]f,g \ge 0[/math] Finding a function g(n) The number of right angled triangles formed by n points will be always less than or equal to the total number of triangles formed by those n points. The total number of traingles formed by n points is the number of ways of choosing 3 points out of the n points. i.e [math]g(n)=^{n}C_3[/math] We have [math]0 \le \frac{{f(n)}}{{n\^3}} \le \frac{{g(n)}}{{n\^3}}[/math] It can be shown that [math]\frac{{g(n)}}{{n\^3}}[/math] converges to 0 as n tends to infinity. Therefore by sandwiching (pinching) [math]\frac{{f(n)}}{{n\^3}}[/math] also must tend to 0 Link to comment Share on other sites More sharing options...
Dave Posted June 27, 2004 Share Posted June 27, 2004 Nicely done, I'd not really thought about it like that. Stumped on the first limit though. Link to comment Share on other sites More sharing options...
bloodhound Posted June 28, 2004 Share Posted June 28, 2004 actually, when i went through it again, my proof if completely wrong. g(n)/n^3 does not converge to 0 as n tends to infinity. it actually tends to 1/6. so my whole proof collapses. but now we know that if the limit of f(n)/n^3 does exist then its bounded above by 1/6. oh well. back to the drawing board now. Link to comment Share on other sites More sharing options...
Freeman Posted June 30, 2004 Share Posted June 30, 2004 Let f(n) denote the maximum number of right triangles determined by n coplanar points. Prove f(n)/(n^2) --> infinity as n-->infinity and f(n)/(n^3) --> 0 as n-->infinity. Lemme get this straight: [math]f(n)/n^2>\infty[/math] as [math]n>\infty[/math] and [math]f(n)/n^3>0[/math] as [math]n>\infty[/math], correct? Or is --> greater than or equal to? Link to comment Share on other sites More sharing options...
bloodhound Posted June 30, 2004 Share Posted June 30, 2004 ---> means tends to . as in a limit. now for the second part. in the first proof i wrote. g(n)/n^3 didnt converge to 0 but if u take g(n)=n then [math]f(n) \le g(n)[/math] [math]\frac{f(n)}{n^3} \le \frac {g(n)}{n^3}[/math] since g(n)/n^3 = 1/n^2 tends to 0 as n tends to infinity then f(n)/n^3 must also tend to 0. Link to comment Share on other sites More sharing options...
fourier jr Posted July 1, 2004 Author Share Posted July 1, 2004 ---> means tends to . as in a limit. yeah, sorry I guess I didn't make that clear enough. I haven't learned Latex so I didn't use limit notation. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now