Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    0
    ReputationRep:
    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?
    Offline

    0
    ReputationRep:
    I get 135. Not sure if it's right though.
    • Thread Starter
    Offline

    0
    ReputationRep:
    can you tell me how to get this answer, because i don't know how to calculate this question, can you explain it?
    thanks!
    (Original post by sephonline)
    I get 135. Not sure if it's right though.
    Offline

    0
    ReputationRep:
    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.
    Offline

    0
    ReputationRep:
    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.
 
 
 
Turn on thread page Beta
Updated: August 17, 2004
Poll
Do I go to The Streets tomorrow night?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.