PR 4 # 17

Wacky · 2006-06-17, 13:28

There are n points on a circle. A straight line segment is drawn between each pair of points. How many intersections are there within the circle if no 3 lines are concurrent?

wblipp · 2006-06-17, 15:23

n*(n-1)*(n^2-5n+6)/24

Pick a point - there are n ways to do that.

Consider sequentially the other points - there are n-1 considerations

For the "ith" other point, there are (i-1) intermediate points on one side and (n-i-1) points on the other side of the line. Thus there are (i-1)*(n-i-1) intersections of the line.

Every intersection has been counted 4 times - once for each endpoint of its lines.

Together this is

(n/4) sum From i=0 to (n-1) of (i-1)*(n-i-1)

Which simplifies to the above.

axn · 2006-06-17, 16:22

(n^2-5n+6) simplifies to (n-2)*(n-3)

wblipp · 2006-06-17, 17:39

That exposes a MUCH simpler derivation.

There are (n choose 4) ways to pick 4 points.
The lines through these 4 points have exactly one crossing,
and ever crossing corresponds to exactly one such set.
So the answer is (n choose 4)

2006-06-17, 13:28	#1
Wacky Jun 2003 The Texas Hill Country 3²×11² Posts	PR 4 # 17 There are n points on a circle. A straight line segment is drawn between each pair of points. How many intersections are there within the circle if no 3 lines are concurrent?

2006-06-17, 15:23	#2
wblipp "William" May 2003 New Haven 2·7·13² Posts	n(n-1)(n^2-5n+6)/24 Pick a point - there are n ways to do that. Consider sequentially the other points - there are n-1 considerations For the "ith" other point, there are (i-1) intermediate points on one side and (n-i-1) points on the other side of the line. Thus there are (i-1)(n-i-1) intersections of the line. Every intersection has been counted 4 times - once for each endpoint of its lines. Together this is (n/4) sum From i=0 to (n-1) of (i-1)(n-i-1) Which simplifies to the above. Last fiddled with by wblipp on 2006-06-17 at 15:28

2006-06-17, 16:22	#3
axn Jun 2003 3²·5·113 Posts	(n^2-5n+6) simplifies to (n-2)*(n-3)

2006-06-17, 17:39	#4
wblipp "William" May 2003 New Haven 2·7·13² Posts	That exposes a MUCH simpler derivation. There are (n choose 4) ways to pick 4 points. The lines through these 4 points have exactly one crossing, and ever crossing corresponds to exactly one such set. So the answer is (n choose 4)