Treebeard's Homepage : Stumpers

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:

Back to Stumper


Last modified .

Copyright © 2003 by Marc Kummel / mkummel@rain.org