Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A question in Permutations and combinations

  1. May 17, 2012 #1
    there are 4 circles and 4 straight lines....find the maximum number of intersecting points possible in the intersection of all these given figures....i cant get how to solve it....
     
  2. jcsd
  3. May 17, 2012 #2
    Do you mean the maximum number of points where they all intersect? Or just at least 2 intersect?
     
  4. May 17, 2012 #3
    A circle can intersect another circle only twice so you would have:
    6 intersects + 4 intersects + 2 intersects= 12

    A straight line can intersect a circle a maximum of twice and there are four circles so:
    8 intersects per line x 4 lines = 32 intersects.

    Each line can also intersect the other lines at a single point so they overlap each of the four lines so not recounting an intersect would be:
    3+2+1=6

    Add them up:
    12+32+6= 50 max intersects

    Someone should check this ;)
     
  5. May 18, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's certainly an upper bound, but it's not immediately obvious that all these intersections are achievable simultaneously.
    Start with some circle C. (This is not one of THE circles, it's just used for construction.)
    You can arrange N equal circles, larger than C, such that each surrounds C. Clearly each pair of these intersects.
    Any M straight lines in general position must intersect each other.
    The region in which the intersections of the lines occurs can be bounded by a circle, D. Shrink that picture as necessary and fit D inside C. Necessarily, every line intersects every circle.
    So any number of circles and lines can be arranged to achieve the upper bound.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A question in Permutations and combinations
Loading...