Results 1 to 9 of 9

Math Help - Number of streets

  1. #1
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340

    Number of streets

    In one residantial area every street crosses over every other street and there are no three streets which crosses each other in same point.

    How many streets there are in that residential area if there are 21 crosses?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by OReilly
    In one residantial area every street crosses over every other street and there are no three streets which crosses each other in same point.

    How many streets there are in that residential area if there are 21 crosses?
    7?

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by CaptainBlack
    7?

    RonL
    Why 7?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by OReilly
    Why 7?
    Because if there are n lines and C(n) crossings, adding an extra line adds
    n more cuts one for each existing line, so:

    C(n+1)=C(n)+n.

    C(1)=0,
    C(2)=1+0
    C(3)=2+1
    C(4)=3+3
    C(5)=4+6
    C(6)=5+10
    C(7)=6+15=21

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by CaptainBlack
    Because if there are n lines and C(n) crossings, adding an extra line adds
    n more cuts one for each existing line, so:

    C(n+1)=C(n)+n.

    C(1)=0,
    C(2)=1+0
    C(3)=2+1
    C(4)=3+3
    C(5)=4+6
    C(6)=5+10
    C(7)=6+15=21

    RonL
    Quite right!
    I have made a picture of how could these streets look like.

    There is also second question.
    How many there are areas which are edged with streets from every side?
    I have counted from picture that there are 15, I must say that I can't think another way at the moment.
    Attached Thumbnails Attached Thumbnails Number of streets-image3.jpg  
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    If you have n lines than at most you can have.
    \frac{n(n-1)}{2} intersection points.
    Thus,
    \frac{n(n-1)}{2}=21
    Thus,
    n^2-n+42=0
    Thus, n=-6,7
    Disregard the negative which yields n=7

    Proof,
    If you have n lines than to maximize the number of intersetion points in a plane you need them to be non-parallel such as no two are parallel to each other* then they need to intersect in such a way that no two pass through the same point. Now for the first line you have n-1 intersection points because it intersects each line EXCEPT for itself thus there are a total of n-1. While the second line interesects at n-2 because it cannot intersect with itself and not with the first because two lines intersect in only one point and it already intersected with the first line, while with the other lines it intersects with other points other than the first. The third one intersects with n-3 and so on. Thus you need to find the sum:
    (n-1)+(n-2)+(n-3)+...+2+1
    Which is \frac{n(n-1)}{2} by the fact of the sum of an arithmetic series.

    *)I did not find a rigorous demonstartion of this argument but if you think about it it is obvious. By that I of course mean the construction is possible.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    I once tried to develope a math riddle based on what you said. Never got to solving it.
    -----------
    The first question of the riddle I answered, i.e. the max number of distinct points.

    The next question which I was not able to solve (hopefully CaptainBlack or rgep can help me out) if given n lines which intersections are possible?

    For example it is possible to position your line in a plane such as there are zero intersections. Namely, all parallel to each other.
    Another example, it is possible to postition your lines in a plane such as there is only one point of interesection. Namely, all lines passes through a common point.

    It is also possible to create n-1 intersections. See it? Position you n-1 lines such as all are parallel to each other. But the last line. Make it a transveral. Thus, you got n-1 intersection points.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ThePerfectHacker
    Which is \frac{n(n-1)}{2} by the fact of the sum of an arithmetic series.
    I didn't want to overburden the reader with unneccessary detail, but
    it is trivial to show that this is the solution of the recurrence in my post,
    which I knew.

    Now if the problem had asked for the number of lines corresponding to
    a maximum number of 7503 crossing points I might have resorted to
    solving the recurrence first, then solving the resulting quadratic.

    RonL
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by OReilly
    .

    There is also second question.
    How many there are areas which are edged with streets from every side?
    I have counted from picture that there are 15, I must say that I can't think another way at the moment.
    This can be solved as the other was by forming a recurence relation for
    the number of regions, and then solving it. I did this a couple of years
    ago when this was (more-or-less) the Geometry Problem of the Week on
    the Math Forum.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: January 16th 2012, 02:21 AM
  2. Replies: 4
    Last Post: April 28th 2011, 07:20 AM
  3. Replies: 2
    Last Post: August 19th 2010, 10:32 PM
  4. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  5. Replies: 5
    Last Post: October 7th 2008, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum