Lines, lines, lines galore

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.

#Combinatorics #Sharky

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

@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 - 5 years, 6 months ago

Oh... that's a great approach!

Julian Poon - 5 years, 6 months ago

I'm getting $6n^{2}$ for a) and as for b), I'm getting overly complicated formulas which are hopefully correct.

Julian Poon - 5 years, 7 months ago

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

Calvin Lin Staff - 5 years, 7 months ago

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

Daniel Liu - 5 years, 7 months ago

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.

Julian Poon - 5 years, 7 months ago

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

Sharky Kesa - 5 years, 7 months ago

@Sharky Kesa – Upon simplification, the answer becomes $\frac{1}{2}n^2\left(17n^2-18n+3\right)$

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 - 5 years, 7 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$