Five-room puzzle

The five-room puzzle is a classical,^[1] popular puzzle involving a large rectangle divided into five "rooms". The objective of the puzzle is to cross each "wall" of the diagram with a continuous line only once.^[2]

As with the Seven Bridges of Königsberg, the puzzle may be represented in graphical form with each room corresponding to a vertex (including the outside area as a room) and two vertices joined by an edge if the rooms have a common wall. Because there is more than one pair of vertices with an odd number of edges, the resulting multigraph does not contain an Eulerian path nor an Eulerian circuit, which means that this puzzle cannot be solved.

By bending the rules, a related puzzle could be solved. For instance, by allowing passage through more than one wall at a time (that is, through a corner of a room), or by solving the puzzle on a torus (doughnut) instead of a flat plane.

Even without using graph theory, it is not difficult to show that the five-room Puzzle has no solution. First, the rules must be clarified. The rooms and the solution line must all be drawn on a single side of a normal flat sheet of paper. The solution line must be continuous, but it can bend sharply or smoothly in any way and can even cross over itself (but not at a wall, so this is often prohibited). The solution line must cross over each "wall" exactly once, where "cross over" means to pass completely from one to the other of the two rooms that are separated by the "wall", or from a room to the area outside the drawing. This precludes "crossing" two walls at the same time by drawing the solution line through the corner at which they meet. It also precludes "crossing" a wall by drawing the solution line up to a wall, perhaps along it, but then leaving the wall on the same side. There are 16 "walls", seven separating rooms and nine separating the rooms from the area outside the drawing.

El método de demostración es la demostración por contradicción . Es decir, procedemos como si existiera una solución y descubrimos algunas propiedades de todas las soluciones. Esto nos coloca en una situación imposible y, por lo tanto, debemos concluir que estábamos equivocados: después de todo, no hay solución. ^{[ 3 ]}

Imaginemos que hay un "observador" en cada "habitación". El observador puede ver la línea de solución cuando está dentro de su habitación, pero no en otras circunstancias. A medida que se dibuja la línea de solución, la verá entrar en su habitación por una pared y salir por otra. También puede observar que la línea comienza y/o termina en su habitación. No hay ningún observador fuera del área del dibujo, por lo que hay cinco observadores.

Consideremos, en primer lugar, a los observadores en las habitaciones inferior izquierda e inferior derecha. Cada una de estas habitaciones tiene cuatro paredes. Si la línea de solución comienza en una de estas habitaciones, su observador verá que la línea sale por una pared. Luego, volverá a entrar en la habitación a través de otra pared y saldrá de nuevo por una tercera. Finalmente, volverá a entrar en la habitación a través de la cuarta pared y terminará. Si la línea de solución comienza en otro lugar, el observador verá que la línea de solución entra y sale de su habitación exactamente dos veces, pasando por las cuatro paredes en algún orden. No hay ningún problema con esto.

Consideremos, sin embargo, a los observadores en las tres habitaciones restantes. Cada una de estas habitaciones tiene cinco paredes. Si la línea de solución comienza en una de estas habitaciones, su observador verá la línea salir (a través de una pared), volver a entrar y salir de nuevo (dos paredes más) y entrar y salir una segunda vez (las dos últimas paredes). Si la línea de solución comienza en otro lugar, el observador verá la línea de solución entrar y salir (dos paredes), entrar y salir una segunda vez (dos paredes más) y finalmente entrar a través de la quinta pared y terminar (se han cruzado las cinco paredes, por lo que la línea no puede volver a salir de la habitación). Así pues, vemos que para las habitaciones con cinco paredes, la línea de solución debe comenzar dentro de la habitación o debe terminar dentro de la habitación. No hay otra posibilidad. En nuestros argumentos, no hemos dicho nada sobre qué paredes cruza exactamente la línea de solución, el orden en que las cruza o hacia dónde va la línea cuando está fuera de una habitación en particular. Por lo tanto, estos argumentos se aplican a todas las soluciones que cumplen las reglas. De nuevo, para las habitaciones con cinco paredes, la línea de solución debe comenzar o terminar dentro de la habitación.

Tenemos tres habitaciones con cinco paredes. La línea de solución tiene un punto de inicio y un punto final, por lo que puede pasar por las cinco paredes de dos de estas habitaciones. Sin embargo, al no tener puntos finales, la línea no puede pasar por todas las paredes de la tercera habitación de cinco paredes. Por lo tanto, no se puede trazar la línea de solución que cumpla con las reglas.

• Gardner, Martin (1959), El libro de Scientific American de acertijos y diversiones matemáticas , Nueva York: Simon and Schuster
• Jacobs, Harold R. (1970), Matemáticas / Un esfuerzo humano , WH Freeman, ISBN 0-7167-0439-0
• Norris, Fletcher R. (1985), Estructuras discretas: una introducción a las matemáticas para la informática , Prentice-Hall, ISBN 9780132152600

• Historia y solución del rompecabezas de la casa de 5 habitaciones del Laboratorio de Arquímedes