33
$\begingroup$

I saw the following problem on 4chan and couldn't solve it:

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ Well, since a 'trough' is 'a channel used to convey a liquid', I'm a bit confused on how to solve this puzzle. It may be a typo! $\endgroup$ Aug 24, 2015 at 19:55

18 Answers 18

42
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ I cannot understand which "other" room you're referring to in "You can start at one room, and end at the other." $\endgroup$ Jul 3, 2014 at 21:48
  • $\begingroup$ @G.T.R, what do you mean which? Any. (I changed it to "another", may be "the" was the problem?) $\endgroup$
    – klm123
    Jul 3, 2014 at 21:49
  • $\begingroup$ OK, but why do you need to go through at least 3 of them ? $\endgroup$ Jul 3, 2014 at 21:54
  • $\begingroup$ @G.T.R, not of them, but of the rest. Because you need to go through all 5 rooms eventually. $\endgroup$
    – klm123
    Jul 3, 2014 at 21:59
  • $\begingroup$ your answer doesn't cover starting outside the rooms, but that just makes it worse anyway $\endgroup$ Jul 4, 2014 at 19:31
49
$\begingroup$

It works when you use a really wide line:

enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ This one cracked me up! $\endgroup$ Jul 26, 2014 at 18:28
36
$\begingroup$

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

$\endgroup$
2
  • 9
    $\begingroup$ +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 $\endgroup$
    – justhalf
    Jul 4, 2014 at 2:49
  • $\begingroup$ HA!, draw a ine through one wall. $\endgroup$
    – Jasen
    Mar 29, 2018 at 9:55
24
$\begingroup$

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

$\endgroup$
20
$\begingroup$

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

$\endgroup$
19
$\begingroup$

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

$\endgroup$
13
$\begingroup$

Credit goes to mathgrant for this answer.

$\endgroup$
0
9
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ How is this different from accepted answer? $\endgroup$
    – klm123
    Jul 4, 2014 at 9:02
  • 5
    $\begingroup$ 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. $\endgroup$ Jul 4, 2014 at 9:16
  • 1
    $\begingroup$ @klm123 This answer is much clearer and easier to understand. $\endgroup$ Jul 4, 2014 at 10:05
8
$\begingroup$

Begin wherever you want and draw one line through all of the doors, but you cannot go through the same door twice. Hard, but possible!

$\endgroup$
1
  • $\begingroup$ Welcome to puzzling.se. I downvoted your answer before I understood it. Now I think you have a good point - that this question could have been posted on 4chan as a lateral thinking question. (If you do an edit on your answer, I can then change to an upvote.) $\endgroup$
    – Len
    Feb 8, 2015 at 7:21
6
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ +1. I think this is valid answer, taking into account formulation of the question. $\endgroup$
    – klm123
    Jul 7, 2014 at 16:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Bobson
    Jul 7, 2014 at 19:12
  • 1
    $\begingroup$ This is not a pipe $\endgroup$ Feb 6, 2015 at 19:00
  • 1
    $\begingroup$ Alternatively, one may figure that most of the gaps on exterior walls are more likely to be windows than doors. $\endgroup$
    – supercat
    Apr 23, 2015 at 16:36
4
$\begingroup$

If we take this puzzle in the spirit in which it was originally created, and not quibble about whether openings are windows or doors, and if we acknowledge that this house represents a house that we could walk from room to room only through the given doors, then, as presented, there is no answer.

IMAGINE, if you will, that this is a life-sized house.

Five-Room House starts with all 16 doors open

When you start, every door is standing open.

  1. Start anywhere and go through each door, but as you go through, close the door behind you so that it becomes a wall.

  2. You cannot walk through a wall.

  3. The only way to solve this puzzle is by cheating.

Euler proved that when a vertex (a room in this example) has an odd number of lines (or in this example, a room that has an odd number of open doors leading out of that room) coming from that point, the answer must either start or end on that vertex.

When we have zero odd vertexes, you can start anywhere and you will find an answer that ends back in the room you started in that will have gone through every door.

When we have two odd vertexes (vertices), the path MUST start in one and end in the other.

When we have four odd vertices, there will be two "odd vertices" that have one unused line, one unused door between them, and no way to get to either of those rooms.

HOW TO CHEAT:

  1. Fold a corner over so that the corner of the diagram is suddenly covered by the blank other side of the paper.

  2. Build your house over a basement. Put a square hole in the floor of the kitchen (one of the five-door rooms, then put a "Wizard of Oz" exit from the basement leading to the outside. (The doors flat in the ground that you lift out of the way to climb up from under the house after a tornado.)

  3. Draw the diagram on a skewed (not evenly baked) bagel, with the bagel hole in the middle of the middle room in the bottom (a room with five doors). Topologically, the outside of the diagram and the inside of the room are now one. You can draw one continuous line starting in the top left room, eventually when you enter that "hole" room the third time, continue that line down through the hole and around to the outside of the house, then go back in the house by one of the other unused. Eventually, you will only have one door left, which will lead you into the top right room.

Five Room House Puzzle drawn on a bagel

Of these three cheats, the bagel is my favorite, but if you use permanent ink marker, I would recommend you don't eat the bagel after math class.

$\endgroup$
1
  • $\begingroup$ If I recall, the donut hole can actually be in any of the rooms and it will still work. $\endgroup$ May 18, 2017 at 0:29
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ To go through a door four times you need to go through it twice first, don't you? $\endgroup$
    – klm123
    Jul 4, 2014 at 15:28
  • $\begingroup$ Yes, but upon going through it a third time, you're no longer going through it "twice" anymore. $\endgroup$
    – user88
    Jul 6, 2014 at 7:31
2
$\begingroup$

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".

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – IQAndreas
    Jul 6, 2014 at 8:30
2
$\begingroup$

graph representation of problem

According to graph theory

Given a graph G, is it possible to find a walk that traverses each line exactly once, goes through ail points, and ends at the starting point? A graph for which this is possible is called eulerian graph.

Thus, an eulerian graph has an eulerian trail, a closed trail containing all points and lines.

  Theorem: The following statements are equivalent for a connected graph G:
    (1) G is eulerian.
    (2) Every point of G has even degree.

In this problem there exists 4 points(nodes) with odd degree. So this is not eulerian graph.

i.e: There no solution existing.

$\endgroup$
1
$\begingroup$

If u Shift this line segment (wall) on either far side u can solve this. However , it was not given anywhere that u can't modify the figure. After all, there are still 5 rooms. In Euler's trail the main cause of failing is this edge's position in the middle. Or else the solution of this puzzle lie in 3d format only. Possible solution

$\endgroup$
1
$\begingroup$

If I remember correctly, this question was originally posed by an MIT professor to his class. I think only 1 student got it by the end of the year.

As I understood it, the question was phrased "With a single line, pass through each plane without breaking each plane twice." There was not any more restrictions on it. I think this version was a simplified version with the doors showing where the planes are to pass through, but it is not limited to a single 2 dimensions.

A valid answer:

Take a sewing thread and stitch your way through the planes, going in and out where needed in the "rooms" to cross each plane only once. If you want to do it with pen and paper, draw like normal through each "door" and then poke a hole in the paper and then continue your line on the other side of the paper and then poke back through to cross the last plane...

$\endgroup$
1
  • $\begingroup$ this seems similar to the bagel solution from Marc Williamson $\endgroup$
    – Jasen
    Mar 29, 2018 at 19:10
0
$\begingroup$

You guys have to think out-side the box (or in this case the 2D screen). If this was on paper we can fold the paper and solve the problem, as shown below. Unless there is a change to the original configuration of doors and walls, this problem is impossible. Hence the warning of "Hard, but possible!"

Fold Paper Solution

$\endgroup$
1
  • $\begingroup$ But ... that doesn't actually go through all the doors, does it? How is this "solution" any different from arbitrarily deciding it's ok to take scissors to the paper and cut off the right half entirely, as you've effectively folded it out of the puzzle? $\endgroup$
    – Rubio
    Mar 23, 2018 at 12:28
-1
$\begingroup$

enter image description here

It took me quite a while to do but I worked it out 😁

$\endgroup$
4
  • $\begingroup$ Your floorplan is not the same as the one in the question. $\endgroup$
    – Gareth McCaughan
    Feb 19, 2019 at 13:49
  • $\begingroup$ No I just took the picture the wrong way up. If you turn it upside down it will look right. I could delete this post and then take another picture the right way up 🤷‍♀️ $\endgroup$ Feb 19, 2019 at 13:52
  • 4
    $\begingroup$ Oops, sorry, I was confused by the upside-down-ness. But what definitely is wrong is that you have used one door twice (near the bottom left in your version of the picture), which you're explicitly forbidden to do. $\endgroup$
    – Gareth McCaughan
    Feb 19, 2019 at 13:52
  • $\begingroup$ Oh ok thanks for telling me 😂 I’m going to try again now lol $\endgroup$ Feb 19, 2019 at 13:55

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