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