Is the following topology puzzle impossible to solve? [duplicate]

Question

There was a problem I was introduced to in grade school which my teacher claimed that not even his graduate level students could solve, and it went a little like this. You have a set of boxes in a brick-like pattern which looks like so:

your challenge is to draw a single line which intersects all walls in the drawing exactly once, but not your line itself. You can start anywhere you like, except on a wall or corner. For example, here is an attempt I made at solving this puzzle:

The circled red walls are walls that still need to be crossed, but I cannot cross them without crossing a wall twice, or crossing my own line.

---

My question comes in not looking for a solution, but an answer. Does this puzzle have a solution, and how do we prove it?

Answer 1

An explanation of this puzzle can be found at https://en.wikipedia.org/wiki/Five_room_puzzle; jafe's answer is the summary form of the reason.

In greater detail, the problem is that you need to have a Eulerian trail through the graph of the puzzle; in order for this to be possible, you must have either exactly zero vertices (rooms) with an odd number of path segments entering, or exactly two such vertices - no other configurations are allowed for solvability. If you have zero such vertices, then all Eulerian paths are closed circuits, and you may start anywhere along the path to solve it; if you have two such vertices, then all paths must start at one of them and end at the other.

This puzzle has four vertices with an odd number of path segments entering: the three large boxes (5 segments each), and the exterior of the drawing (9 segments). Since four "odd" vertices is neither zero odd vertices nor two odd vertices, the puzzle has no Eulerian paths, and is thus not solvable.

Answer 2

How many boxes have an odd number of walls? You can have a maximum of two in any solution, i.e. the starting box and the end box. All other boxes you exit once for each entry, making total visited walls an even number.

In this one there are three boxes with an odd number of walls, so it's not solvable.

Answer 3

The problem is impossible to solve (even for graduate students).

For each area, you must enter and leave it an even number of times.
Unless you either start or finish inside the area.
If there are two areas or fewer having an odd number of walls, that is possible.
But in the diagram there are 3 areas with 5 walls.
So you can start / finish in 2 of the areas, but you can't leave the other area without crossing a wall twice.

Answer 4

No, this puzzle is not solvable

Consider that, with respect to the 5 rectangles that make up this figure, each line crossing will either move you from the inside to the outside of a rectangle, or from the outside to the inside. And, after moving inside, the next crossing must take you outside. From left to right, top to bottom, the number of bordering lines on the boxes are:

• 5
• 5
• 4
• 5
• 5

This puzzle would only be solvable if exactly 0 or 2 boxes had an odd number of lines in its perimeter. This is for the exact same reason why you can draw the left figure below without lifting your pencil, but not the right:

When passing the pencil through a vertex, you have to enter and then leave, adding 2 lines to it. The only exception to this is the start and end; you either end where you started, resulting in 0 vertices with an odd number of lines, or you don't, resulting in 2. This principle holds for the rectangle puzzle, replacing vertices with boxes and drawing lines with crossing them.