# Maximum number of triangles formed by points on a square?

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

-
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
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
show 5 more comments

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

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

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