Alguien q me recuerde la demostración de porque este problema no tiene solución?
Gracias 
PD: Si alguien piensa que tiene solución, que lo intente hacer.
oues parece xungo
Pero todos sabemos que la acometida de la luz ha de ir por encima de la del agua asi que srry es una xorrada
creo que tenia que ver con la planaridad de un grafo.
edito:
En teoría de grafos, un grafo planar es un grafo que puede ser dibujado (los matemáticos se refieren más formalmente como "embebido" en un plano) sin que ninguna arista se interesecte
En la práctica, es difícil usar el teorema de Kuratowski para decidir rápidamente si un grafo es planar. Sin embargo existe un algoritmo rápido para este problema: para un grafo de n vértices y e el número de aristas, es posible determinar en tiempo O(n) (lineal) si el grafo es planar o no.
Teorema 1. Si n ≥ 3 entonces e ≤ 3n - 6
Teorema 2. Si n > 3 y no existen ciclos de longitud 3, entonces e ≤ 2n - 4 
Si en un grafo en más de dos puntos confluyen un número impar de líneas no tiene solución 
Sólo puede haber dos puntos con confluencia impar, que son los puntos que se usarán para comenzar y para terminar. (Evidentemente este no se puede, porque los tres necesitan tres líneas respectivamente).
aki esta como se resuelve en un video http://uncutvideo.latino.aol.com/videos/8b651af945c20d4554c898fab0d3ba0d
PD:a mi me salio xD
pues a mi me ha salido:
http://img509.imageshack.us/img509/8758/iwinxx1.jpg
no lo intenteis si no sabeis darle al boton derecho.
Hay varias maneras de demostrar que no existe solución a eso. Creo recordar que la más sencilla es utilizando la fórmula de Euler que se da en todos los grafos planos (y que también sirve para poliedros):
Caras + Vértices = Aristas + 2.
Por construcción, la solución del problema tiene que tener 6 vértices (las casas y los servicios) y 9 aristas (las conexiones de cada casa a los tres servicios). Por lo tanto, por esa fórmula (que habría que demostrar también, claro) tendría que tener 9 caras.
Sin embargo, por otra parte, podemos ver que cada cara de la solución ha de tener al menos 4 aristas, ya que tiene que ser de la forma casa -> servicio -> casa -> servicio o bien casa -> servicio -> casa -> servicio -> casa -> servicio (unir dos casas o dos servicios entre sí no tiene sentido).
Si cada cara tiene al menos cuatro aristas, el número de aristas de la solución es al menos (5*4)/2 = 10. (cinco caras, cuatro caras por arista, y cada arista se está contando dos veces, de ahí la división).
Esto contradice la fórmula de Euler. Ergo, la solución no puede existir.
Q.E.D.
