Is It Possible to Walk Through This House Using Each Door Exactly Once?

[zh3zh3]

Homework Statement

______________x___
|ooooo|ooooo|ooooo|
xoooooxoooooxooooox
|__x__|__x__|__x__|
|ooooo|ooooo|ooooo|
|oooooxooooo|ooooo|
|__x__|_____|__x__|

Sorry for the bad diagram.
The problem is like this:
Is it possible to walk in and out of the house below so that each door of the house is used exactly once? Please give reasons.
Show how blocking one of the door will change the results in your answer above.

Homework Equations

The Attempt at a Solution

Either I misinterpreted the question wrongly, or I'm just too dumb to solve this question.
First I assume that the question needs me to end up OUTSIDE the house.
This means I have to start from inside the house, but no matter at which point I start with I can't find the answer.
Then I assume that I can end up anywhere I want as long as I use up all the doors.
The results are still the same because:
|
--|-- The problem that I can see is at the left most cross point of the walls.
|

I tried to label the doors as vertices and connect them as in graphs, and it seemed to me the problem requires me to solve it using the concept of Euler circuit. But it is just too awkward. I can't get the solution no matter how hard I try. (even blocking a door, but I definitely can get the solution if I could block two doors.)

 

[marcusl]

Actually I think your diagram is great. How about going through the rooms in the following order

in
1 4 5
2 3 6
out

 

[Defennder]

I don't see how that attempt works. I tried it out and there's at least one door which is unpassed.

 

[HallsofIvy]

This looks like the general "Konigsberg" problem. To pass through a region (room) you must use two bridges (doors). You can pass through any room with an even number of doors but you must begin and end in a room with an odd number of doors. Since, here, the outside is counted as a "room", there are three rooms with an odd number of doors. This can't be done, it is impossible.

 

[D H]

Is it possible to walk in and out of the house below so that each door of the house is used exactly once? Please give reasons.

The problem is not necessarily to find a solution. What if no solution exists?

I tried to label the doors as vertices and connect them as in graphs, and it seemed to me the problem requires me to solve it using the concept of Euler circuit.

You're on the right track here. This a graph with seven nodes (the six rooms plus the outside of the house) and eleven vertices (the doors).

An Eulerian circuit starts and ends at the same node. This is not what you are asked to do. You are asked to start in one of the rooms and end outside: An Eulerian path. What are the conditions on the graph that make an Eulerian path possible (or impossible)?

 

[D H]

Since, here, the outside is counted as a "room", there are three rooms with an odd number of doors.

I count for rooms with an odd number doors: The outside, the two rooms on the left, and the top middle room. Still impossible, of course. Judiciously blocking off one door does lead to a solution.

 

[HallsofIvy]

Oh, you are right. For some reason, I had counted the door between the two rooms on the left only for the top room! Still, as you say, since that is larger than two, it is impossible.

 

[zh3zh3]

Honestly speaking this question was given as an assignment by my discrete math lecturer. The question alone took 24/100 of the marks.

And I was stuck whether it is possible to get a solution.

Also, I was curious about the two rooms on the right. They serve no purpose from what I can see. We're basically ending up in this diagram because no matter what you do, you still have to take all the entrances on the right, even blocking either of the doors which ends up giving an extra dead end.

_____________
|ooooo|ooooo|
xoooooxooooox
|__x__|__x__|
|ooooo|ooooo|
|oooooxooooo|
|__x__|_____|

So I was wondering did I (and probably everyone who replied in the post) actually misunderstood what the question really wants? Because it seems just too simple to give "No solution" as a solution to my questions.

 

[zh3zh3]

______________x___
|ooooo|ooooo|ooooo|
xoooooxoooooxooooox
|_____|__x__|__x__|
|ooooo|ooooo|ooooo|
|oooooxooooo|ooooo|
|__x__|_____|__x__|

OK I was thinking of this.
I'll label the rooms in order:
1 2 3
4 5 6
I'll close the door at the south of the room number 1.

Then, it goes like this:
4 > 5 > 2 > 3 > Exit through the north door
3 (enter through the east door) > 6 > Exit
1 > 2

And there we used up all the doors exactly once, though we eventually ended up inside the house. Of course we could just start from the house and end up outside (just reverse the order of my solution above)

Seems logical?

 

[Defennder]

Your solution works if the setup has been changed to that in your latest reply. But unfortunately there is a missing door between rooms 1 and 4 which is present in your original post and your solution does not cover that.

 

[zh3zh3]

Is it possible to walk in and out of the house below so that each door of the house is used exactly once? Please give reasons.
Show how blocking one of the door will change the results in your answer above.

Yes, initially there was a door between room 1 and 4.
And like what you all have said, it is impossible to pass through each door of the house.

But my second question was how blocking one door can change the results in the answer above.

Well I'm not sure if that's what the question wants, but I think that's the only solution that seems probable.

 

[lukas86]

I read briefly over most of the posts, but from what I collected, you have to walk into and exit the house but can do this several times. You cannot use a door twice.

Now if you have to enter, you must exit the house. Since there is 5 doors on the exterior of the house, you enter... exit... enter... exit... enter again. You can use all the doors once and hit all the doors, but you'd be left inside the house.

 

[D H]

So I was wondering did I (and probably everyone who replied in the post) actually misunderstood what the question really wants? Because it seems just too simple to give "No solution" as a solution to my questions.

Saying there is no solution without justification is easy and weak. What if someone smarter than you found a solution? On the other hand, saying there is no solution and here's why: ... is very powerful. If the "and here's why" is correct, that means that even the most clever problem solver in the world will never find a solution.

Your solution works if the setup has been changed to that in your latest reply. But unfortunately there is a missing door between rooms 1 and 4 which is present in your original post and your solution does not cover that.

The second part of the problem is to determine if blocking (i.e., removing) one door will change the answer.

Then, it goes like this:
4 > 5 > 2 > 3 > Exit through the north door
3 (enter through the east door) > 6 > Exit
1 > 2

Almost! You missed one door and you also started and ended inside the house. Using the missed door will solve both problems.

This is a problem in graph theory. The key is to look at the arrangement as a graph. All you have to do is examine the nodes (rooms) with an odd number of vertices (doors). An Eulerian path of the graph exists if and only if the number of such nodes is either zero or two. No solution can exist if the number of nodes with an odd number of vertices is one or three or more. If the number of such nodes is two, the two nodes with an odd number of vertices must be the nodes at the start and end of the path.

 

[zh3zh3]

Agree.

I would say that the question is solved, I think. I'm sorry that the question was vague though, as in never telling where would you start or where would you end up. I've learned Euler paths in class, though I'm not quite good with it. But anyhow, thanks to all that helped and replied my question.

(PS: And yes my life would be so much easier if the question had that missing door :D )