Walls & Lines

A popular classic puzzle that involves a large square divided into 5 "rooms". The object of the puzzle is to cross each "wall" of the diagram with a continuous line only once.

(note the uncrossed wall - marked with circle)

Solution

The proof is as follows: "A continuous line that enters and leaves one of the rectangular rooms must of necessity cross two walls. Since the three bigger rooms have each an odd number of walls to be crossed, it follows that an end of a line must be inside each if all the 16 walls are crossed. But a continuous line has only two ends, so the puzzle is unsolvable."

One can also see the problem in a graph theory approach, with each room being a vertex and each wall being an edge of a graph. The objective is to find an Eulerian path for the obtained graph. This problem is similar to the Seven Bridges of Königsberg problem, having the same explanation to the nonexistence of a solution.