不是我这人直肠子，为得一个鼠标，出那么难的题，老吴你也太抠了。如果我这个答案有效的话，就把鼠标送我女朋友吧，我在剑桥先谢谢您了。嘎嘎嘎嘎
这道题是英国最有名的谜题专家Henry Ernest Dudeney创作的，如果想要通过常规的解法，根本不可能。我在网上查了很多资料，通过jordan的双线理论和欧拉定理都可以很容易的证明在同一平面内不能建立所有的有效链接。后面的有两个理论的证明资料。原版的题目叫Oil,Water and Gas Puzzle,我现在在英国留学，我问过了，另外的名字叫Three utilities and Three horses.非常非常有名的谜题。下面的原题，和lw的差不多，不过更直观
Oil, Water and Gas Puzzle  | Version I: Can three houses be connected to three utilities concurrently, without the pipes crossing on any dimensional plane?
Version II: Draw this puzzle on a piece of paper, and without lifting the pen from the paper or crossing lines, connect the utilities to the three houses.
|
迄今为止，有三个办法可以解决这个问题，都是使用的trick，一个是抓住字眼，题目中只说了管道不可以交叉，但却没说管道pipe不可以穿过房子，所以，下面的这个版本的答案就孕育而生了：
Oil, Water and Gas Puzzle Version I: It is not possible to connect the three utilities to all three houses without crossing pipes in the same plane. However, the usual quibble is to solve the puzzle by running one of the pipes underneath one of houses on its way to another house; the puzzle's instructions forbid crossing other *pipes*, but not crossing other *houses*.
第二种答案同样是运用技巧，在纸上打一个小洞，或者让管道画到纸的边缘后转到背后 ，让管道通过小洞或者纸面边缘翻转转到纸的背面画，这样就不用相交了。哈哈哈，真弱智。
Version II: Without using tricks, it can't be done. One trick is to draw a line to one corner of the paper, raise the corner, with the pen tip still touching it, and then lower it on the final point to complete the puzzle.
第三种解决方案比较让大家认可，建立一个管道的空间，等于是把平面扭曲成三维，链接如下：
Another trick is to set the problem on a toroid (doughnut-shaped object).
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 用jordan线性理论证明的
| 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.
[ 本帖最后由 caily 于 2007-9-9 08:50 编辑 ] |
发表于 2007-9-8 23:02
| 
发表于 2007-9-9 11:44
| 
.
