Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

I saw the following problem on 4chanenter image description here

And couldn't solve it.

It's very likely to be some kind of troll (no solution).

I'm hoping to see some rigorous proofs that disprove the existence of such a line.

share|improve this question

10 Answers 10

up vote 15 down vote accepted

It is impossible.

Quite the same problem is "Seven Bridges of Königsberg", it was solved (proven) by Euler.

  1. Suppose you have drawn such a line and follow it from one room to another. Since you must use each door you must have a look at each room out of 5. What are these rooms?

  2. There will be 3 (at least) rooms you always go through - if you enter it you always exit it later.
    Indeed, 1 (at most) room you can start at, and another 1 (at most) room you can finish at, but others you must go through: $5-1-1 = 3$.

  3. Since you use each door exactly once, the mentioned 3 rooms must have an even number of doors, since you entry them the same number of times you exit them. But you have only 2 rooms with an even number of doors, the others have 5 doors. So you could not draw such a line.

share|improve this answer
    
I cannot understand which "other" room you're referring to in "You can start at one room, and end at the other." –  LeGrandDODOM Jul 3 at 21:48
    
@G.T.R, what do you mean which? Any. (I changed it to "another", may be "the" was the problem?) –  klm123 Jul 3 at 21:49
    
OK, but why do you need to go through at least 3 of them ? –  LeGrandDODOM Jul 3 at 21:54
    
@G.T.R, not of them, but of the rest. Because you need to go through all 5 rooms eventually. –  klm123 Jul 3 at 21:59
    
Everything makes sense now, thanks ! –  LeGrandDODOM Jul 3 at 22:02

Just for fun:

Actually, there is solution, which formally satisfies all the rules. You just need to walk through a wall!
Hard, but possible! enter image description here

share|improve this answer
7  
+1. I think this is the troll solution envisioned by the poster in 4chan, because it satisfies the rules! Nobody says you can't walk through a wall. Hard, but possible! Haha –  justhalf Jul 4 at 2:49

You can draw a graph with six vertices, one for each room and one for the outside. Draw an edge to represent each door. The puzzle asks for an Eulerian path, which can be done if no more than two vertices have an odd number of edges coming in. In this graph the top two rooms, the middle bottom room, and the outside all have an odd number of edges coming in, so in the usual way there is no such path. A sketch is below. ABCDE are the rooms in the same locations as in the picture, F is outside, and the lines are connections through doors. ABD and F all have an odd number of edges coming in.

enter image description here

share|improve this answer

It works when you use a really wide line:

enter image description here

share|improve this answer
1  
This one cracked me up! –  Shashank Sawant Jul 26 at 18:28

Similar to klm's solution, this one requires a little bit of lateral thinking but doesn't actually involve walking through a wall. Instead, you have to fold the corner of the piece of paper that the picture is drawn on, to form a bridge over a wall.

enter image description here

share|improve this answer

It is actually impossible if you consider walking through walls impossible as stated in the other answers. That can be explained by graphs or in another similar, but yet easier to understand way:

Ignoring the connections between the rooms, you have 5 rooms:

3 rooms with 5 doors and 2 rooms with 4 doors.

  • if a room has an even amount of doors, there are two ways it can be part of the solution: either the line starts and ends within that room and all other doors are used to both enter and leave the room or the line passes through (amount of doors / 2) times.
  • if a room has an uneven amount of doors, there are another two ways it can be part of the solution: either the line starts within that room and all the other doors are used to both enter and leave or the line ends within that room and all the other doors are used to both enter and leave.

This gives us the insight that there are 3 rooms that need to contain either the start or the end of the line and there are 2 rooms that might contain both start and end. Following that logic, we have at least 2 of either start or end of the line and thus we can't use just a single line to solve this problem.

share|improve this answer
1  
How is this different from accepted answer? –  klm123 Jul 4 at 9:02
3  
I believe that my answer is easier to understand and that mine is more organised. Additionally, in my case, it does not matter if the rooms are adjacent or placed far away from each other since I only consider the connectors (the doors) and don't bother with the meta concept of doors and paths. This would only be neccessary if there was a room that only connects to other rooms and not to the "outside world". My answer is directed mostly at the people that don't get what the poster of the accepted answer wanted to say. –  Fredchen777 Jul 4 at 9:16
1  
@klm123 This answer is much clearer and easier to understand. –  DisgruntledGoat Jul 4 at 10:05

Alternatively, going "through" a door need not necessarily be interpreted in the same way as one would in a house.

This single, continuous line passes exactly once through each door, which is the constraint in the original question. Of course, it also conveniently side-steps making any other assumptions and takes certain liberties with the walls.

enter image description here

share|improve this answer

As far as I can tell there are no doors in this image, therefore any line will cross every doors and no line will cross a door twice: just draw a line anywhere. Actually you might have already draw some lines of length 0.

EDIT: some people seem to think this is a troll, maybe they simply don't know what universal and existential quantification mean, or they disagree with the fact that there are no door on the image ?

share|improve this answer
    
+1. I think this is valid answer, taking into account formulation of the question. –  klm123 Jul 7 at 16:20
2  
Ara, I think it'd help if you explicitly said "There are no doors, just doorways" rather than just "there are no doors" without replacing them. –  Bobson Jul 7 at 19:12

This "puzzle" can be described as an Euler Trail, and was discussed in a video by James Grime in which he proves why the puzzle is impossible:

The gist of it is, every time you enter a room, you have to leave it as well, which means all doors come in pairs (the door you entered the room with, and the door you left the room with). The only time you can have an odd number of doors is in two cases: if you start the path in that room, or end in that room.

If we look at the image, two of the rooms have 4 doors (an even number), while three of the rooms have 5 doors (an odd number). This means if we start in the top left room, make our path, then end in the top right room, the bottom center room will have been walked through an even amount of times, meaning one of the doors will have remained unused and inaccessible. Therefore, it is indeed a "troll puzzle".

share|improve this answer
    
Although it doesn't apply to this example, you can also have a valid room layout where there are an even number of doors in all rooms, in that case you go back to and end in the room you started in. –  IQAndreas Jul 6 at 8:30

Even assuming that it is not allowed to draw the line through a "wall", there is another kind of troll solution. You are forbidden to go through the same door twice, but you can go through that door four times. Then it is easy to do it.

Or you could maintain that there are no door at all in the drawing, just $12$ disconnected pieces of "wall". This makes it a non-problem.

share|improve this answer
    
To go through a door four times you need to go through it twice first, don't you? –  klm123 Jul 4 at 15:28
    
Yes, but upon going through it a third time, you're no longer going through it "twice" anymore. –  Joe Z. Jul 6 at 7:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.