Very Strange House

1. Mar 25, 2009

M12

Imagine that the picture shown below is an overhead view of the layout of five rooms in a very strange house. The reason that this house is so strange is that every room has a doorway on every single wall. Your task is to find a continuous path that passes through every doorway exactly once.

http://img258.imageshack.us/img258/5387/3dhouse.th.jpg [Broken]

The image below is an example of an unsuccessful attempt to solve this problem. The path shown in the diagram passes through every doorway except for one. There is no way to reach the final doorway without passing through one of the doorways twice!

http://img516.imageshack.us/img516/558/exampley.th.jpg [Broken]

Hint: To make it easier, just copy - paste the image onto paint, erase the previous blue lines, and have fun figuring it out!

P.S. If you do figure this out, please share! I've tried almost every possible way and I still can't figure it out. Thanks!

Last edited by a moderator: May 4, 2017
2. Mar 26, 2009

Rogerio

Well,
suppose there is a path.
Each room with an odd number of doors has to be the start or the end of the path.
But there are 3 rooms like that.
So it is impossible.

Last edited: Mar 26, 2009
3. May 15, 2009

vedang444

yup.. tried all ways.. even intersected paths... it is impossible because 1 doorway always remains...

4. May 15, 2009

AUMathTutor

Seems similar to the bridges of konigsburg problem. A graph has an Eulerian path iff the there exist precisely two vertices of odd degree. Three vertices of odd degree <=> no Eurlerian path.