Railway lines

There are five towns no three of which lie on a straight line. They must be connected by a railway line composed of four straight tracks. Bridge crossings are permitted; the lines are supposed to have different levels at the crossing points.
How many different railway lines can be constructed?

Reply 1

sephonline

I get 135. Not sure if it's right though.

Reply 2

winlinux

can you tell me how to get this answer, because i don't know how to calculate this question, can you explain it?
thanks!

sephonline

I get 135. Not sure if it's right though.

Reply 3

Spleenus`

I get 120 by doing 5 x 4 x 3 x 2 but it's not a properly thought out answer. It makes sense when I think about it but I can't be bothered to explain my method of thinking.

Reply 4

sephonline

I'll try my best to explain it. Instead of using "railway lines" and "towns", I'll use "lines" and "points" to simplify the language.

First of all, by trial-and-error it is easy to check that for 2 points, only 1 line is possible, where as for 3 points, 3 lines are possible and for 4 points, 16 are possible.

Observe that for 5 points, if a line is drawn between each pair of points, there are 4 + 3 + 2 + 1 = 10 lines in total (imagine a pentagon with a star inside).

Since you only want 4 lines connecting your points, there are 10C4 = 210 possible combinations of choosing 4 lines from 10 lines. This is the maximum number of combinations.

However, the figure 210 is an overestimate as some combinations of 4 lines will lead to 1 point not being connected to the rest of the graph.

Without loss of generality, take any point A. Imagine this as the point which is not connected to the rest of the graph. For the remaining 4 points, 6 distinct lines can be drawn to connect each of them. Then, there are 6C4 = 15 ways to choose 4 lines from those 6.

Since you could have chosen any point out of the original 5 as A, the total overestimate = 15*5 = 75. Subtracting this from 210 gives 135.

........... That didn't make much sense. I'll be happy to clarify.