Treebeard's Stumper Answer 2 May 2003

A Grand Tour of Dunn Middle School

Take a grand tour of Dunn Middle School when you visit the DMS Science Fair on Friday! Here is a sketch that shows every building with all rooms and doorways. Closets and rooms with only a single entry are not included. Can you find a path through school that takes you through each doorway just once, without passing through any doorway a second time? We removed an entire wall last summer to enlarge Genevieve's room, so I suppose we could also make a few new doorways to solve this stumper, but only the smallest number of new doorways necessary.

I recommend you save this floorplan image and print out a few full-page copies to play with.

You will quickly discover that it is not possible to do a grand tour. Which building is the biggest problem? The real stumper is where to add the fewest number of extra doors to make it possible. You can start inside or out, and there's no requirement to end up where you started, but it's a bonus if you do!

I'm so embarrassed - I forgot an outside door in my own building! It was covered up with posters and a table and lots of "stuff", but we needed to uncover it to move in Trevor and Bryan's bicycle-powered TV for science fair. The new doorway is just below the door on the left side of the top "Marc" building. How does that change this stumper?

You'll quickly discover that you can't tour DMS going through each doorway just once. Notice the problem is always a room with three doors. If a room has two doorways, you can enter and leave. If it has any even number of doors, you can enter and leave multiple times. But if it has an odd number of doorways, it must be a place where you start or finish. (Think of the outside as one more big room.) DMS has too many odd rooms! My best solution requires four extra doors so that odd Donna can take the grand tour and end up in odd Lynne's office.

Notes:

Here's one elegent solution with a DMS Grand Tour from Donna to Lynne that doesn't cross the path:

However you blast new doorways, you must end up with just two odd-number rooms and all the rest even-number. This gets complicated because every new doorway changes the door count of two rooms (including the outside).

I'm sure that blasting four new doorways is the minimum. Donna and Cynthia and Art are all odd, and there are five odd rooms in the lower-right office building. That's eight odd rooms, and 8/2 = 4. Is a four-door path still possible with the extra doorway in my room??

I'm short on time right now, so I gave this stumper to my students at school with a 15 minute time limit to collect some data. Out of 60+ kids at school, 16 kids found four-door solutions and 30 kids found solutions with five doors or more. It was interesting that most four-door solutions ended up in the hall. At first I thought that might mean something, but now I think it's just because it's so hard to draw extra doorways in that small room. Kids who started outside never did better than five-doors.

Here are a few starting web links for your own research:

• This is an update of one of my old stumpers on A Grand Tour of the Science Building (May 9, 1997). I've since moved to a new science building and my old building has been updated too!

• This is a math problem in graph theory, a branch of topology that has nothing to do with making graphs of data. School math classes seem over-burdened with curriculum and testing requirements. I think it is important (and refreshing) to introduce kids to these different math problems that have nothing to do with computation and manipulating symbols. It's interesting that the kids who get these problems in my classes are not always the top math students. I worry that we might lose a generation of potential mathematicians with this regimen.

• The original graph theory stumper is about the Bridges of Königsberg. The puzzle is to find a way to walk all seven bridges over the River Pregel without crossing any bridge twice. Sound familiar?

  The analysis by Leonard Euler (1707-1783) is considered to be the beginning of both modern graph theory and topology. Euler's idea was to simplify the network to an abstract geometry of pure relationship. Since more than two points have an odd number of connections, a single path is not possible. A single walk is possible with just one more bridge, but where?

  Here's how modern graph theory and topology simplify and abstract this stumper. All vertices are odd in the final graph, so there is no solution.
  

  

• There's good info and many more links about graph theory here, here, here, here, and here.

• I have more graph theory stumpers including Four-Color Christmas (4 December 1999), Getting Around (30 April 1999), Twisted Wires (18 April 1997), and A Grand Tour of the Science Building (9 May 1997).

Back to Stumper

Last modified .