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

Home > Shapes > Geometry
Counting Crossings (Posted on 2014-10-08) Difficulty: 3 of 5
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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information