# FMM9

### From charlesreid1

# 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.) |

## Flags

Friday Morning Math ProblemsSpider Socks and Shoes FMM1 Sums of Powers of 2 FMM2 Fifty Coins FMM3 The Zeta Monogram FMM4 The Cthulhus Monogram FMM4B Multiplication Logic FMM5 The Termite and the Cube FMM6 Sharing Dump Trucks FMM7 The Flippant Juror FMM8 Bus Routes FMM9 A Robust Bus System FMM9B Square-Free Sequence FMM10 Inferring Rule from Sequence FMM11 Checkerboard Color Schemes FMM12 One-Handed Chords FMM13 First Ace FMM14 Which Color Cab FMM15 Petersburg Paradox Revisited FMM16 A Binomial Challenge FMM17 A Radical Sum FMM18 Memorable Phone Numbers FMM19 Arrange in Order FMM20 A Pair of Dice Games: FMM21
Category:Puzzles · Template:FMMFlag · e |