Five room puzzle: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to: navigation, search
(Solution)
Line 4: Line 4:
 
== Solution ==
 
== 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 possible."
+
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 impossible."
   
 
One can also see the problem in a [[graph theory]] approach, with each room being a [[vertex_(graph_theory)|vertex]] and each wall being an [[edge_(graph_theory)|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.
 
One can also see the problem in a [[graph theory]] approach, with each room being a [[vertex_(graph_theory)|vertex]] and each wall being an [[edge_(graph_theory)|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.
 
[[Category:Puzzles]]
 
[[Category:Puzzles]]
  +
[[Link title]]

Revision as of 04:38, 2 December 2008

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.

WallsLines.gif WallsLines2.gif (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 impossible."

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. Link title