El rompecabezas de las cinco habitaciones es un clásico [1] rompecabezas popular que implica 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]
Al igual que en el caso de los Siete Puentes de Königsberg , el rompecabezas puede representarse en forma gráfica con cada habitación correspondiente a un vértice (incluyendo el área exterior como habitación) y dos vértices unidos por una arista 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 modificar 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 una superficie plana.
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, deben aclararse las reglas. Las habitaciones y la línea de solución deben dibujarse todas en un solo lado 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 a 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 excluye "cruzar" dos paredes al mismo tiempo dibujando la línea de solución a través de la esquina en la que se encuentran. También excluye "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 "paredes", siete que separan habitaciones y nueve que separan las habitaciones del área fuera del 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]
Imagina 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 en cualquier otro lugar. 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.
Consideremos, en primer lugar, a los observadores de las habitaciones de la parte inferior izquierda y de la parte inferior derecha. Cada una de estas habitaciones tiene cuatro paredes. Si la línea de solución comienza en una de estas habitaciones, el observador verá que la línea sale a través de una pared. Luego regresará a la habitación a través de otra pared y saldrá de nuevo a través de 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 ningún problema con nada de 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 (las cinco paredes han sido cruzadas, por lo que la línea no puede volver a salir de la habitación). Por lo tanto, 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 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 pasar por las cinco paredes de dos de estas habitaciones. Sin embargo, al quedarse sin extremos, la línea no puede pasar por 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.