물, 가스, 전기 공급의 문제

 그림과 같이 가,나,다, 이렇게 세 집이 있고, 물 공급원, 가스 공급원, 그리고 전기 공급원이 아래에 순서대로 있다. 교차하지 않게 선을 그어 물, 가스, 전기 모두를 세 집에 다 공급하려면 어떻게 해야할까?

 듀드니의 문제이다.(http://en.wikipedia.org/wiki/Water,_gas,_and_electricity)

해답.

이런 경우에는 용어에서 속임수나 트릭을 찾아야한다고 듀드니는 설명했다.[1] 위 그림 처럼 물의 관을 가 집 지하에 만들어 다 집으로 보내면 해결이라는 것이다.

(근데 지하 매설이 가능하면 그냥 다 지하에 파묻어버리면 그만 아닌가?)

 만약 위와 같은 꼼수를 부리지 않는다면 이 문제는 풀 방법이 없다. 이는 그래프 이론에 의거한 것으로 3, 3의 이분그래프(Bipartite Graph)는 평면 상에 교차 없이 그릴 수 없다는 정리가 있다. 이 정리의 엄밀한 증명은 오일러 공식(v-e+r=2)를 써서 불가능함을 보인다. 지면이 적어 여기서는 생략한다.

 

[1] 천재들이 즐기는 수학퍼즐게임(한다 료스케 지음, 이정환 옮김, 일출봉) p207