Este clásico y popular rompecabezas [1] consiste en un gran rectángulo dividido en cinco "habitaciones". El objetivo del rompecabezas es cruzar cada "pared" del diagrama con una línea continua solo una vez. [2]
Soluciones
Al igual que con los Siete Puentes de Königsberg , el rompecabezas se puede representar en forma gráfica con cada habitación correspondiente a un vértice (incluyendo el área exterior como una habitación) y dos vértices unidos por un borde si las habitaciones tienen una pared común. Debido a que hay más de un par de vértices con un número impar de aristas, el multigraph resultante no contiene una trayectoria euleriana ni un circuito euleriano , lo que significa que este rompecabezas no se puede resolver.
Al doblar las reglas, se podría resolver un rompecabezas relacionado. Por ejemplo, permitiendo el paso a través de más de una pared a la vez (es decir, a través de una esquina de una habitación) o resolviendo el rompecabezas en un toro (rosquilla) en lugar de en un plano.
Prueba informal de imposibilidad
Incluso sin utilizar la teoría de grafos, no es difícil demostrar que el rompecabezas de las cinco habitaciones no tiene solución. Primero, las reglas deben aclararse. Las habitaciones y la línea de solución deben dibujarse en una sola cara de una hoja de papel plana normal. La línea de solución debe ser continua, pero puede doblarse bruscamente o suavemente de cualquier manera e incluso puede cruzarse sobre sí misma (pero no en una pared, por lo que esto a menudo está prohibido). La línea de solución debe cruzar cada "muro" exactamente una vez, donde "cruzar" significa pasar completamente de una a otra de las dos habitaciones que están separadas por la "pared", o de una habitación al área fuera del dibujo. . Esto evita "cruzar" dos paredes al mismo tiempo trazando la línea de solución a través de la esquina en la que se encuentran. También impide "cruzar" una pared dibujando la línea de solución hasta una pared, quizás a lo largo de ella, pero luego dejando la pared en el mismo lado. Hay 16 "muros", siete cuartos de separación y nueve que separan los cuartos del área exterior al dibujo.
El método de prueba es prueba por contradicción . Es decir, procedemos como si existiera una solución y descubrimos algunas propiedades de todas las soluciones. Estos nos ponen en una situación imposible y, por lo tanto, tenemos que concluir que estábamos equivocados; después de todo, no hay solución. [3]
Imagínese que hay un "observador" en cada "habitación". El observador puede ver la línea de solución cuando está en su habitación, pero no de otra manera. A medida que se dibuja la línea de solución, la verá entrar en su habitación a través de una pared y salir por otra. También puede ver que la línea comienza en su habitación y / o termina en su habitación. No hay ningún observador en el área fuera del dibujo, por lo que hay cinco observadores.
Considere, en primer lugar, a los observadores de las salas inferior izquierda y 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 a través de una pared. Luego volverá a la habitación a través de otra pared y saldrá de nuevo por una tercera. Finalmente, regresará a 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 problema con nada de esto.
Considere, sin embargo, a los observadores en las tres salas 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á que la línea se va (a través de una pared), vuelve a entrar y sale de nuevo (dos paredes más) y entra y sale por segunda vez (las dos últimas paredes). Si la línea de solución comienza en otro lugar, el observador verá que la línea de solución entra y sale (dos paredes), entra y sale por segunda vez (dos paredes más) y finalmente entra por la quinta pared y termina (las cinco paredes se han cruzado , para que la línea no pueda volver a salir de la habitación). Entonces, 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 exactamente qué paredes cruza 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 obedecen a las reglas. Nuevamente, para las habitaciones con cinco paredes, la línea de solución debe comenzar o terminar dentro de la habitación.
Pero tenemos tres habitaciones con cinco paredes. La línea de solución tiene un comienzo y un final, por lo que puede atravesar las cinco paredes de dos de estas habitaciones. Sin embargo, habiéndose quedado sin extremos, la línea no puede atravesar todas las paredes de la tercera habitación de cinco paredes. Por lo tanto, la línea de solución no se puede trazar para obedecer las reglas.
Notas
- ^ Gardner , 1959 , p. 112 Gardner titula el problema (rompecabezas) como "Cruzar la red" y se refiere a él como uno de los rompecabezas topológicos más antiguos.
- ↑ Según Norris 1985 , p.207 "A menudo se encuentran gráficos eulerianos como rompecabezas. Considere el famoso plano de planta que consta de cinco habitaciones interconectadas entre sí y con el exterior por puertas en cada pared. El rompecabezas es comenzar en una habitación o en el afuera, atraviese cada puerta exactamente una vez y regrese al punto de partida ".
- ↑ Este argumento es una expansión del esbozado por Jacobs (1970 , págs. 489-491).
Referencias
- Gardner, Martin (1959), The Scientific American book of Mathematical Puzzles and Diversions , 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
enlaces externos
- Historia y solución al rompecabezas de la casa de 5 habitaciones por Archimedes Laboratory