| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 824.1 | That's one drafty house, let me tell you | AKQJ10::YARBROUGH | Why is computing so labor intensive? | Fri Feb 05 1988 13:44 | 32 |
| +----d-----+-----d-----+-----d-----+
| | | |
d d d d
| | | |
+----d-----+--d--+--d--+-----d-----+
| | |
d d d
| | |
+--------d-------+-------d---------+
As there are 3 rooms with an odd number of doors (and the outside of the
house has an odd number of doors), the path(s) passing through all the
doors must have at least 4 ends if the layout is planar. If the layout is
on a torus with the hole passing through one of those rooms you can do it,
as the effect of the hole is to make the number of 'doors' even in that
room (and the outside).
Next question: How many doors have the property that if you seal off that
one door, the problem is solvable? Answer follows the <FF>.
8. Any of the ones marked X below.
+----d-----+-----X-----+-----d-----+
| | | |
d d d d
| | | |
+----d-----+--X--+--X--+-----d-----+
| | |
X X X
| | |
+--------X-------+-------X---------+
|
| 824.2 | Correct | STAR::HEERMANCE | Martin, Bugs 5 - Martin 0 | Fri Feb 05 1988 16:01 | 11 |
| Re .1
I guess you get a gold star. A torus is the correct topology to
solve this problem. Is it the only one?
As an exercise in graph making, a node-edge graph can be drawn to
demonstrate that closing a door is essentially the elimination of
an edge between two nodes. This can be used as a proof for .1
assertion about closing a door.
Martin H.
|
| 824.3 | | CLT::GILBERT | Builder | Fri Feb 05 1988 17:00 | 6 |
| There is a path iff there are 0 or 2 areas with an odd number of
door. Since there are 4 areas with an odd number of doors in the
floor plan, and a sealed door reduces the number of doors in two
(adjacent) areas by one, the sealed door must connect two of the
odd-doored areas. You'll note that these are the doors that Lynn
marked.
|
| 824.4 | | TLE::BRETT | | Fri Feb 05 1988 19:56 | 5 |
|
Hence the space formed by equivalencing two such rooms also
is a valid solution to the problem...
/Bevin
|
| 824.5 | Other solutions... | CHOVAX::YOUNG | Back from the Shadows Again, | Sat Feb 06 1988 03:09 | 4 |
| Any surface of Genus > 0 has mappings that produce a solution, as
do many unusual mappings to topologies of indeterminat Genus.
-- Barry
|