Let \(n\) be a positive integer. On each side of a square \(n\) points are chosen. (No point is at a vertex of the square.)

(a) How many segments are there whose endpoints are two of the above points and such that no segment lies along a side of the square?

(b) What is the maximal possible number of intersection points of the segment from part (a)?

Give proof.

## Comments

Sort by:

TopNewest@Julian Poon As I said, do it in a similar way for a). Of course, that assumes that you did a) in a "smart" way.

So, my way of doing a is: There are \( {4n \choose 2 } \) segments, of which \( 4 \times { n \choose 2 } \) of them lie on a side of the square. Hence, there are \( \frac{ 4n (4n-1) } { 2} - 4 \times \frac{ n(n-1) } { 2} = 6n^2 \) pairs of such lines.

Use a similar approach to do b:

Hint:Given any 4 points, there is at most 1 way to get an intersection point.Hint:How many sets of 4 points are there, which involve 3 or more points on the same line segment?Hint:If in a set of 4 points, no 3 of them lie on the same line segment, then there is exactly 1 way to get an intersection point, and this doesn't involve a line segment on the side of the square.Hence, the answer is

\[ { 4n \choose 4 } - 5 \times { n \choose 3 } \times 3n - 4 \times { n \choose 4 } = \frac{1}{2} n^2 ( 17n^2 - 18n + 3 ). \] – Calvin Lin Staff · 1 year, 8 months ago

Log in to reply

– Julian Poon · 1 year, 8 months ago

Oh... that's a great approach!Log in to reply

I'm getting \(6n^{2}\) for a) and as for b), I'm getting overly complicated formulas which are hopefully correct. – Julian Poon · 1 year, 8 months ago

Log in to reply

\[\left(9n^2\sum _{k=1}^{n-1}k\right)-\left(\sum _{k=1}^{n-1}\sum _{j=1}^{3n}kj\right) + \left(n\sum _{k=1}^n\sum _{j=1}^{2n}\left(j-1+3\left(k-1\right)\right)\right)-\left(\sum _{k=1}^n\sum _{j=1}^{2n}\left(k-1\right)j\right) + \left(n\sum _{k=1}^n\sum _{j=1}^n\left(2j+\left(3k-5\right)\right)\right)-\left(\sum _{k=1}^n\sum _{j=1}^n\left(k-1\right)j\right)\]

Goodbye and good luck.

I can elaborate on how I counted it if you want, but there are many other ways to do so. – Julian Poon · 1 year, 8 months ago

Log in to reply

– Sharky Kesa · 1 year, 8 months ago

Elaborate please. Your formula might be able to be simplified via peer help.Log in to reply

To get the answer, I first split the question up into \(3\) different groups, group A, B and C. For each group, the numbers represent the order in which I would draw the lines. I would draw the lines in Group A first, then group B and finally group C. When drawing these lines, I would count the lines it would intersect.

So for example, the first point I am going to entertain would be Point 1 in group A. After drawing all the lines that are connected to that point, I would get 0 intersections.

Next, I would entertain the second point in group A. After drawing all the lines connecting to that point, I would get <Some function in terms of n> intersections.

And so on.

After doing this for Group A, B and C, I get that the number of intersections for

Group A: \(\left(9n^2\sum _{k=1}^{n-1}k\right)-\left(\sum _{k=1}^{n-1}\sum _{j=1}^{3n}kj\right)\)

Group B: \(\left(n\sum _{k=1}^n\sum _{j=1}^{2n}\left(j-1+3\left(k-1\right)\right)\right)-\left(\sum _{k=1}^n\sum _{j=1}^{2n}\left(k-1\right)j\right)\)

And Group C: \(\left(n\sum _{k=1}^n\sum _{j=1}^n\left(2j+\left(3k-5\right)\right)\right)-\left(\sum _{k=1}^n\sum _{j=1}^n\left(k-1\right)j\right)\)

I have "verified" the formula for accuracy by drawing out and manually counting the number of intersections for case \(n=1,2,3\). The numbers matched. – Julian Poon · 1 year, 8 months ago

Log in to reply

– Daniel Liu · 1 year, 8 months ago

Note that b) is maximized when any two segments that don't share an endpoint intersect.Log in to reply

– Calvin Lin Staff · 1 year, 8 months ago

Don't over complicate b. Do it in a similar way to a.Log in to reply