老吴还卖关子！我看不下去了！
1。http://www.supuzzle.com/supuzzle.html
这是题目的出处，是flash格式，可以在线玩。大家可以在线去玩玩！
2。http://mathforum.org/dr.math/faq/faq.3utilities.html
这里用了拓扑学的两种不同方法证明了题目是无解的。
There are three houses and three utilities:
 You must draw a line from each house to each utility, without the lines ever crossing. Can you connect the houses to the utilities?
This problem is impossible. At least, it's impossible to connect the houses to the utilities on a flat sheet of paper. In fact, it's impossible in the Euclidean plane (a flat sheet stretched to infinity) and on most other two-dimensional surfaces. Some people have a trick to get around the problem: they send a gas, water, or electric line through one of the houses. Of course, real utility companies don't need tricks. The real world is three-dimensional, so power lines can go over or under each other.
The three utilities puzzle can be solved on a special kind of two-dimensional surface. This special place is the outside of a torus. A torus is shaped like a perfect doughnut, with a hole in the middle. You can see a movie of a flat surface becoming a torus at Alexander Bogomolny's page about Paper Strip Activities. Here's one solution:
 A piece of paper with a hole in it is like a torus that has been squashed flat. This means that the three utilities problem can also be solved by cutting a hole in the center of a piece of paper. Lines are allowed to go around the sides of the paper, or through the hole to the other side.
Why can't you connect the houses to the utilities on a normal sheet of paper? The answer uses a branch of mathematics called graph theory. A graph is a collection of points, which are called "nodes" or "vertices," connected by lines, which are called "edges." A "planar graph" is a graph that can be drawn in a flat plane without any of the edges crossing. We are trying to connect the houses to the utilities as a planar graph. There are at least two ways to use graph theory to prove that the utilities problem is impossible.
Using the Jordan Curve Theorem
| Let's start by drawing lines from some of the utilities to some of the houses: gas -> house 1 -> electricity -> house 2 -> water -> house 3. |  | | If we draw one more line, from house 3 to the gas company, then we have a loop. Notice that our loop has an inside and an outside. |  |
The Jordan Curve Theorem tells us that the loop will have an inside and an outside no matter how we stretch or curve our lines, as long as they don't cross.
Now, we still have three lines left to draw: from house 1 to the water company, house 2 to the gas company, and house 3 to the electric company. Because we don't want to cross the lines we have already drawn, we have to choose whether to draw these new lines inside or outside our loop. | That means two lines will have to be either outside or inside the loop. These two lines will have to cross. |  |
Using Euler's Formula
We have already seen vertices, or nodes, and edges: in our problem, the vertices are the houses and utility companies, and the edges are the lines between them. Another important object in graph theory is a "face." Faces in graph theory are a lot like the six faces of a cube. They're the area inside a closed loop of edges. There can't be any vertices in the middle of a face. Leonhard Euler found a formula to relate the number of faces, edges, and vertices in a planar graph:
F - E + V = 2,
where F is the number of faces, E is the number of edges, and V is the number of vertices. This formula counts the area outside the graph as one of the faces.
Now, let's pretend we have a solution to the utility problem. There are six vertices, one for each house and utility company. Because each of the three utility companies is connected to three houses, we have 3 * 3 = 9 edges. Let's see what we can figure out about the faces.
We know that the boundary of every face is a closed loop of edges, and we know that every edge goes between a house and a utility company. There's no reason to go from a house to a utility and back to the same house.
| That means the boundary of a face could either be house 1 - utility 1 - house 2 - utility 2 (four edges): | 
| | or house 1 - utility 1 - house 2 - utility 2 - house 3 - utility 3 (six edges): |  |
Now let's use Euler's formula to figure out how many faces there are:
F - E + V = 2
F = 2 + E - V
= 2 + 9 - 6
= 5 faces.
Every face has at least four edges, so the number of edges in all the faces is at least 4 * 5 = 20 edges. This counts each edge twice, because every edge is a boundary for two faces. So, the smallest number of edges is 20 / 2 = 10 edges. However, we know that there are only 9 edges! Since nothing can have nine edges and ten edges at the same time, drawing a solution to the three utilities problem must be impossible.
3。http://www.youtube.com/watch?v=piLfZHn_8HE
这个视频显示了用作弊的方法解出了这道题。 |
发表于 2007-9-7 13:02
| 
.
