Lines, lines, lines galore

Let nn be a positive integer. On each side of a square nn 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.

Note by Sharky Kesa
4 years, 1 month ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

@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 (4n2) {4n \choose 2 } segments, of which 4×(n2) 4 \times { n \choose 2 } of them lie on a side of the square. Hence, there are 4n(4n1)24×n(n1)2=6n2 \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

(4n4)5×(n3)×3n4×(n4)=12n2(17n218n+3). { 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 - 4 years ago

Log in to reply

Oh... that's a great approach!

Julian Poon - 4 years ago

Log in to reply

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

Julian Poon - 4 years, 1 month ago

Log in to reply

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

Calvin Lin Staff - 4 years, 1 month ago

Log in to reply

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

Daniel Liu - 4 years, 1 month ago

Log in to reply

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

(9n2k=1n1k)(k=1n1j=13nkj)+(nk=1nj=12n(j1+3(k1)))(k=1nj=12n(k1)j)+(nk=1nj=1n(2j+(3k5)))(k=1nj=1n(k1)j)\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 - 4 years, 1 month ago

Log in to reply

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

Sharky Kesa - 4 years ago

Log in to reply

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

To get the answer, I first split the question up into 33 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: (9n2k=1n1k)(k=1n1j=13nkj)\left(9n^2\sum _{k=1}^{n-1}k\right)-\left(\sum _{k=1}^{n-1}\sum _{j=1}^{3n}kj\right)

Group B: (nk=1nj=12n(j1+3(k1)))(k=1nj=12n(k1)j)\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: (nk=1nj=1n(2j+(3k5)))(k=1nj=1n(k1)j)\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,3n=1,2,3. The numbers matched.

Julian Poon - 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...