2
$\begingroup$

$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.

  • 0
    @Covi, we do not delete posts which have already gotten answers—even less when the answers have been upvoted.2011-11-23

3 Answers 3

2

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$.

  • 0
    @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?2011-03-02
0

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.

  • 0
    For general case of N I only figured a solution using mathematical induction...2011-03-02
-3

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 ]

  • 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.2012-08-23