Originally Posted by OReilly
RonL
Quite right!Originally Posted by CaptainBlack
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.
If you have lines than at most you can have.
intersection points.
Thus,
Thus,
Thus,
Disregard the negative which yields
Proof,
If you have 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 intersection points because it intersects each line EXCEPT for itself thus there are a total of . While the second line interesects at 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 and so on. Thus you need to find the sum:
Which is 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.
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 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 intersections. See it? Position you lines such as all are parallel to each other. But the last line. Make it a transveral. Thus, you got intersection points.
I didn't want to overburden the reader with unneccessary detail, butOriginally Posted by ThePerfectHacker
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
This can be solved as the other was by forming a recurence relation forOriginally Posted by OReilly
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