miniatura| Diagrama do problema das tres casas nun plano. pódense facer todas as conexións dos servizos, mais dúas delas están a cruzarse.
O problema das tres casas, tamén coñecido como problema dos tres servizos públicos, é un crebacabezas matemático que pide que se tracen conexións non cruzadas entre tres casas e tres compañías de servizos públicos nun plano.
Ao formulalo a principios do século XX, Henry Dudeney escribiu que xa era un vello problema. É un crebacabezas imposíbel: non é posíbel facer as nove conexións sen que ningunha delas se cruce.
Pódense resolver versións do problema en superficies non planas como un toro ou unha banda de Möbius, ou que permiten que as conexións pasen por outras vivendas ou servizos públicos.
Enunciado O problema das tres casas pódese expresar do seguinte xeito:
En termos de teoría de grafos máis formais, o problema pregúntase se o grafo bipartito completo é un grafo plano. Este grafo ten seis vértices en dous subconxuntos de tres: un vértice para cada casa e un para cada servizo.
Ten nove arestas, unha aresta para cada un dos aparellos dunha casa cun servizo, ou máis abstractamente unha aresta para cada par de vértices un deles nun subconxunto e un vértice no outro subconxunto.
Os grafos planos son os grafos que se poden debuxar sen se cruzaren as liñas no plano, e se se puidese atopar tal debuxo, resolvería o enigma dos tres servizos.; see p. 409.
Solucións do crebacabezas
Sen solución miniatura| Proba sen palabras: elimínase temporalmente unha casa. As liñas que ligan as vivendas restantes cos servizos públicos dividen o plano en tres rexións. Sexa cal sexa a rexión na que se coloque a casa eliminada, a utilidade sombreada do mesmo xeito está fóra da rexión. Segundo o teorema da curva de Jordan, unha liña que os ligue debe cortar unha das liñas existentes. Tal e como adoita presentarse (nun plano bidimensional plano), a resposta ao crebacabezas de utilidade é "non ten solución": non hai forma de facer as nove conexións sen que ningunha das liñas se cruce entre si.
Noutras palabras, o grafo non é plano. Kazimierz Kuratowski afirmou en 1930 que non é plano, do que se desprende que o problema non ten solución. porén, afirma que "Curiosamente, Kuratowski non publicou unha proba detallada de que [] non é plano".
Unha proba da imposibilidade de atopar un mergullo plano de utiliza unha análise de casos que inclúe o teorema da curva de Jordan. Nesta solución, examínanse diferentes posibilidades para as localizacións dos vértices en relación aos 4 ciclos do grafo e móstrase que todos son inconsistentes cun mergullo plano.
Mudando as regras
é un grafo toroidal, o que significa que se pode mergullar sen cruzamentos nun toro, unha superficie do genus un. Estes mergullos resolven versións do quebracabezas nas que as casas e empresas están debuxadas nunha cunca de café ou outra superficie semellante en lugar de nunha superficie plana. Mesmo hai suficiente liberdade adicional no toro para resolver unha versión do quebracabezas con catro casas e catro servizos. Do mesmo xeito, se o crebacabezas dos tres servizos se presenta nunha folla de material transparente, pode resolverse despois de torcer e pegar a folla para formar unha fita de Möbius.. ver Figura 7, p. 292.
Outra forma de mudar as regras do quebracabezas que o farían solucionable, suxerida por Henry Dudeney, é permitir que as liñas de servizos públicos pasen por outras casas ou servizos públicos distintos dos que ligan.. A solución dada en pp. 200–201 implica pasar unha liña por unha das outras casas.
Notas
Véxase tamén
Outros artigos Grafo plano Retícula (grupo)
Ligazóns externas 3 Utilities Puzzle at Cut-the-knot The Utilities Puzzle explained and "solved" at Archimedes-lab.org
Categoría:Topoloxía Categoría:Teoría de grafos Categoría:Problemas matemáticos Categoría:Matemáticas recreativas