# Number of streets

• Apr 24th 2006, 04:13 AM
OReilly
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?
• Apr 24th 2006, 05:19 AM
CaptainBlack
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
• Apr 24th 2006, 06:45 AM
OReilly
Quote:

Originally Posted by CaptainBlack
$7?$

RonL

Why 7?
• Apr 24th 2006, 07:42 AM
CaptainBlack
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
• Apr 24th 2006, 04:12 PM
OReilly
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. :D
• Apr 24th 2006, 05:50 PM
ThePerfectHacker
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.
• Apr 24th 2006, 05:57 PM
ThePerfectHacker
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 :mad: (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.
• Apr 24th 2006, 11:36 PM
CaptainBlack
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
• Apr 25th 2006, 12:51 PM
CaptainBlack
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. :D

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