Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$N$ points are to be put on sides of a square. What's the maximum number of triangles which are formed by joining those points?

Hints would be appreciated.

share|improve this question
2  
By "joining those points", do you mean joining each pair of points by a line segment? –  joriki Mar 2 '11 at 4:43
    
Can you give an equation for "the number of triangles" given the relative data, e.g. the number of points on each side? Or is it more complicated than that? –  Yuval Filmus Mar 2 '11 at 4:57
    
@joriki Joining points in sets of three (because a triangle has three points =).) –  Covi Mar 2 '11 at 7:04
    
@Filmus The problem doesn't limit how you arrange these N points on four sides. And I guess this is why it asks for the maximum number. –  Covi Mar 2 '11 at 7:04
5  
This is a problem on a mathcamp admissions exam. Applicants are not supposed to look for help online. –  user7688 Mar 2 '11 at 8:40

3 Answers 3

Each triangle requires exactly three points, but not every set of three points defines a triangle. There are $n\choose 3$ sets of three points. You have to get rid of sets where all three points fall on the same side of the square. If $S_i$ points are on side $i$ of the square, $\sum_{i=1}^4 {{S_i}\choose 3}$ sets of three don't make triangles, and must be subtracted out. Since you're looking for the maximum number of triangles, minimize $\sum_{i=1}^4 {{S_i}\choose 3}$ subject to $S_1+S_2+S_3+S_4 = N$.

share|improve this answer
    
How to minimize $\sum_{i=1}^4 {{S_i}\choose 3}$? –  Covi Mar 2 '11 at 7:09
    
@Covi: Consider a situation where it's possible to move a point from the side it's on to another side where it will have fewer companions than before. Would that increase or decrease the number of triangles that can be formed? What does that tell about the maximizing distribution? –  joriki Mar 2 '11 at 8:25

Seems like you'd rather put the question here than have me a feast haha.... Expand the formula given above, then this problem is simply an integer inequality. A little trick is required :-). For N=4k this would be a bit easier.

share|improve this answer
    
For general case of N I only figured a solution using mathematical induction... –  dementrock Mar 2 '11 at 8:32

This is my own formula : correct me if I'm wrong ,

n^2 C3 - 2n x nC3 - 2 * [ (n-1)C3+ (n-2)C3 +....3C3 ]

share|improve this answer
6  
If you'd show how you'd come up with this formula I am sure that someone will be able to tell you better whether you are right or wrong. Mathematics is not magical formulas appearing from nowhere. One needs to justify the choice of formula too. –  Asaf Karagila Aug 23 '12 at 10:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.