In the capital of the grand country of Appelhaken there is a plane garden containing four magnificent monuments. So magnificent are they that the country has a Law requiring that there must be a clearly marked carpeted path all the way from each monument in the garden to each other monument, and no two such paths may share parts or intersect.
A fifth monument is installed. In order to comply with the Law, the best architect in all of Appelhaken designs a grand and magnificent bridge in the garden, and one path is laid on top of the bridge while another is laid underneath it, for without this bridge the Law could not be upheld.
Shortly afterwards, two more monuments are installed, but there is no more money for additional bridges because the first bridge was too grand. How can the chief gardener of Appelhaken reroute paths to preserve the Law?
Hint:
The bridge might need to be used for several paths.
Answer
Four monuments
Easy map to draw:
Or, topologically equivalently (and more usefully for our purposes):
Five monuments
Starting from the last map above:
(Green is the bridge, with one path crossing over it.)
Seven monuments
Starting from the five-monument map above:
The two new monuments are in red, and new paths in thin lines.Left red can be connected directly (no bridge use) to three blues: top left, top right, bottom left.
Right red can be connected directly (no bridge use) to three blues: top right, middle, bottom right.We draw in these six paths right away with thin black lines, but in two cases (left red to top left blue, right red to middle blue), we must choose which side of the existing mini-path (leading up to the bridge) to put the new path. We make the choice in such a way as to block off further access to the top right blue, which is now connected to everything so we don't need it any more.
The remaining paths (left red to middle and bottom right; right red to top left and bottom left; red to red) must cross the bridge. We draw these paths carefully so that they don't cross each other. I've used thin red lines for paths to the right of the existing path on the bridge, thin blue lines for paths to the left of the existing path on the bridge, and the red-to-red path could be on either side so it doesn't matter and I've just used a thin black line.
No comments:
Post a Comment