Treebeard's Homepage : Stumpers

# Treebeard's Stumper Answer30 April 1999

Getting Around

Getting around to all the kids' exhibits at the DMS Science Fair on Friday night will be hard enough. (That's 5 - 8 p.m., with BBQ and softball!) This stumper is also hard to get around. The picture below shows a rectangle with five pairs of spots. The task is to draw lines connecting the spots with the same letters, A to A, B to B, and so on. Your lines may not cross each other, or leave the rectangle, or cross the solid barriers between AD and BC. If you can't get it, try leaving it alone for a day and then try again.

It is possible to connect the spots in the stumper without crossing lines. (See below.) These graph theory problems are very real for the design of electronic circuit boards, since signals will short-circuit if any paths cross. Christian got it first. He tried at night, and then saw it right away the next morning. I don't know why that helps, but I had the same experience. Several kids assumed they could only use straight lines, which shows how assumptions can get in the way. Often some kind of lateral thinking is required to see a solution!

Notes:

I swiped this stumper from Martin Gardner's "Graph Theory" chapter in his classic 6th Book of Mathematical Diversions from Scientific American (University of Chicago Press, 1971). He relates that "graph theory" goes back to pioneering work by the German mathematician Dénes König in the 1930s. It's really a branch of topology dealing with patterns of connections, and has nothing to do with the graphing data in the usual sense.

Many DMS students got the answer once Christian proved it's possible. Michael and Sam came up with different solutions which add extra loops here and there.

The Three Utilities stumper is a graph theory classic: Can the three houses be connected to the three utilities without the lines crossing?

```+-----+          +-----+          +-----+
|HOUSE|          |HOUSE|          |HOUSE|
|  1  |          |  2  |          |  3  |
+-----+          +-----+          +-----+

+-----+          +-----+          +-----+
|power|          |water|          | gas |
+-----+          +-----+          +-----+
```
This is not possible unless you run one of the lines underneath one of houses. (The puzzle's instructions forbid crossing other utility lines, but not crossing other houses.) What's the simplist graph that can't be done without crossing lines?

Back to Stumper