FMM9

Friday Morning Math Problem

Bus Routes

A certain city has 10 bus routes. Is it possible to arrange the routes and the bus stops so that if one route is closed, it is still possible to get from any one stop to any other (possibly changing buses along the way), but if any two routes are closed, there are at least two stops such that it is impossible to get from one to the other?

Hint: Bus lines must have at least two stops on their line (otherwise, it's not a very useful bus line!), and in fact each bus line can have as many bus stops as you'd like.

All bus stops are served by at least one bus line, if all bus lines are operating.

Try using a two step process: first, lay out the 10 bus lines, and decide where to put the stops. second, close bus lines and see how the stops are affected.

Solution

YES! It is possible The circle solution (10 bus lines connecting one by one in a circle) is the simplest solution. But there are others. For example: consider 10 straight lines in a plane, with no two lines being parallel, and no three lines meeting at any one point. (Lines = bus routes, intersections = bus stops.) Now you can extend the lines so multiple lines will intersect at multiple bus stops. If you discard one bus line, it is still possible to get from any one stop to any other stop. But if you remove two bus lines, the bus stop that is the intersection of those two bus lines will not have any bus lines servicing it, so it is not possible to get from that bus stop to any other bus stop (and therefore is a valid solution that satisfies the constraints). (Also note that bus stops serviced by only one line are disallowed by the problem constraints that any one bus line can be removed and all stops are still reachable from all other stops.)