All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Counting Crossings (Posted on 2014-10-08)
3 lines in a plane can be easily be drawn such that there are 0, 1, 2 or 3 points where at least 2 of them cross.

What are the possible numbers of crossing points for 4, 5, or 6 lines?

Can any of these results be generalized?

 No Solution Yet Submitted by Jer Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 To sleep, perchance to dream | Comment 4 of 7 |
For n lines, the following are always possible:

0 intersections -- all lines parallel

1 intersection -- all lines go through a single point

n-1 points -- this can be done in at least two ways
a) n-1 parallel lines, and the nth is not parallel to any of them
b) n-1 lines go through a single point, and the nth is parallel to one of the others

n points -- n-1 lines go through a single point, and the nth is not parallel to any of the others and does not go through that single point

n*(n-1)/2 -- no shared intersections, no parallel lines, so every line forms a unique intersection with any other line

So far:
With 4 lines one can have 0,1,3,4 and 6 intersections.
Also, 5 is possible if there are no shared intersections, and two of the lines are parallel.
/**************************/
With 5 lines one can have 0,1,4,5 and 10 intersections.  Not sure how many others are available.
6 is possible, if 3 lines are parallel to each other, and the other two are parallel to each other, so there are 3*2 intersections.
/**************************/
With 6 lines one can have 0,1, 5, 6 and 15 intersections.  Not sure how many others are available.

6 can be partitioned as 2+4  and 3+3 and 2+2+2,  so 8 and 9 intersections are also possible as a result of intersecting parallel lines. because 8 = 2*4 = 2*2*2 and 9 = 3*3.

Also, if k lines share a single intersection (where k > 3) and the other (n-k) lines are parallel to each other but to none of the other lines, then there are 1+k(n-k) intersections.
(n,k) = (6,4) is another way of getting to 9
(n,k) = (6,3) gives rise to 10 intersections
(n,n-1) = n, which I have listed above

Also, if k lines share a single intersection (where k > 2) and the other (n-k) lines are parallel to each and to one of the first k lines, then there are 1+(k-1)(n-k) intersections.
(n,k) = (6,3) gives rise to 7 intersections
(n,k) = (6,4) is another way of getting to 7
(n,n-1) = n-1, which I have listed above

So far, for 6 lines, I have 0,1, 5, 6, 7, 8, 9,10 and 15 intersections, but I feel that I have not yet exhausted the possibilities.  Gotta go to sleep

Edited on October 9, 2014, 7:37 am
 Posted by Steve Herman on 2014-10-08 21:49:15

 Search: Search body:
Forums (0)