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.

  • 2
    By "joining those points", do you mean joining each pair of points by a line segment?2011-03-02
  • 0
    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?2011-03-02
  • 0
    @joriki Joining points in sets of three (because a triangle has three points =).)2011-03-02
  • 0
    @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.2011-03-02
  • 0
    @Covi: Your answer seems to imply that only triangles having the given points as vertices are counted. I had understood the question to refer to any triangles formed, including triangles that are formed within the square by vertices formed by crossing lines.2011-03-02
  • 0
    @joriki Indeed, only triangles having the given points as vertices are counted.2011-03-02
  • 5
    This is a problem on a mathcamp admissions exam. Applicants are not supposed to look for help online.2011-03-02
  • 0
    @april Sorry. Though I was not asking for SOLUTIONS, just hints. I think the rule says if cited properly outside help could be used. I will close the discussion anyway.2011-03-02
  • 0
    @Covi: THere are no discussions here. I have rolled back to the original version.2011-03-02
  • 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
    How to minimize $\sum_{i=1}^4 {{S_i}\choose 3}$?2011-03-02
  • 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