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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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 ). \]

Log in to reply

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.

Log in to reply

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

Log in to reply

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

Log in to reply

UPDATE: I'm so done with this question. Through systematic counting, the solution for b) is

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

Log in to reply

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.

Log in to reply