Tuesday, September 7, 2010

The Hateful Neighbors

The Boggis, Bunce, and Bean families were once united in their pursuit of a common enemy, but have since developed a bitter and irreconcilable hatred for one another.  Each family lives in its own house in its own part of town, and all is well and good, so long as members of different families don't cross paths - if they do, they will start brawling until the poor sheriff has to come out and break them up.  They are very civil indoors, however. 

Each family needs to be able to access the post office, the general store, and the sheriff's office without encountering members of other families.

So the sheriff has come up with a great plan; draw up plans for each family to have its own three paths, traveling from each home to a each of the three municipal buildings.  In this way, for example, the Boggis family has three paths, where each path leads from its front door to the front doors of the post office, general store, and sheriff's office.  Can he do this without letting the paths cross, and without digging any tunnels or building any bridges - in other words, working in a two-dimensional plane?

Solution: Unfortunately, there is none.  There is no way to create three sets of paths to three locations without them crossing or meeting.