El rompecabezas de cinco habitaciones es un rompecabezas clásico y popular que involucra un gran rectángulo dividido en cinco "habitaciones". El objetivo del rompecabezas es cruzar cada "pared" del diagrama con una línea continua una sola vez. [2]
Al igual que con los Siete Puentes de Königsberg , el rompecabezas se puede representar de forma gráfica con cada habitación correspondiente a un vértice (incluida la zona exterior como 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 multigrafo resultante no contiene un camino euleriano ni un circuito euleriano , lo que significa que este rompecabezas no se puede resolver.
Al infringir las reglas, se podría resolver un enigma 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 toroide (donut) en lugar de en un plano.
Incluso sin utilizar la teoría de grafos, no es difícil demostrar que el rompecabezas de las cinco habitaciones no tiene solución. En primer lugar, es necesario aclarar las reglas. Las habitaciones y la línea de solución deben dibujarse en una sola cara de una hoja de papel normal. La línea de solución debe ser continua, pero puede doblarse brusca 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 "pared" 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 impide "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, tal vez a lo largo de ella, pero luego dejando la pared en el mismo lado. Hay 16 "paredes", siete habitaciones que separan y nueve que separan las habitaciones del área exterior al dibujo.
El método de prueba es la prueba 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, tenemos que 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á en su habitación, pero no de otra manera. A medida que se traza la línea de solución, verá que entra a su habitación por una pared y sale 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.
Consideremos, en primer lugar, a los observadores en 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á la línea salir a través de una pared. Luego volverá a entrar en la habitación por otra pared y volverá a salir por una tercera. Finalmente, volverá 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á la línea de solución entrar y salir de su habitación exactamente dos veces, pasando a través de las cuatro paredes en algún orden. No hay ningún problema con nada de esto.
Consideremos, 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á la línea salir (a través de una pared), volver a entrar y salir (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 por la quinta pared y terminar (las cinco paredes han sido cruzadas). , por lo que la línea no puede 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 exactamente 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 tanto, estos argumentos se aplican a todas las soluciones que obedecen 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 inicio y un final, por lo que puede atravesar las cinco paredes de dos de estas habitaciones. Sin embargo, al quedarse sin extremos, la línea no puede atravesar todas las paredes de la tercera habitación de cinco paredes. Por lo tanto, no se puede trazar la línea de solución para obedecer las reglas.