# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Ghost Post
Icarian Member

 Posted: Mon Feb 12, 2001 5:42 pm    Post subject: 1 As with the solution to the first edition of this problem, we can see that there is no path or asteroid configuration that will allow us to pass through each door only once. Using some graph theory, construct a graph representing this shed in the following way: Each room is a vertex (label it using the room's name) and let's add a vertex for "outside labeled "O". Add an edge for each door, the edge connects whichever vertices that the door allow passage between. Note that this graph is connected and that the vertices O, C, and E are of odd degree. The solution we are looking for is whether this graph has a Eulerian trail. A Eulerian Trail is a walk on the edges of a graph which uses each edge (door) exactly once. A Connected Graph has an Eulerian trail Iff it has at most two Vertices of Odd Degree. Therefore there is no Eulerian Trai in the orignal configuration. Topology changes the graph (basically, in anyway we want). Keep in mind all vetices connect to O because they have exterior doors (that lead outside) but we can now create topolgies that allow us to make rooms E & C adjacent (or any room for that matter), so these now become even vertices.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersGhost Post Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum