Board logo

标题: 寻找天才 有奖竞猜 [结束获奖会员pontifex ] [打印本页]
作者: dv2d4admin    时间: 2007-9-6 11:20     标题: 寻找天才 有奖竞猜 [结束获奖会员pontifex ]

首先： 大家辛苦啦！

答案在：46楼！http://www.nb591.com/viewthread.php?tid=47279&page=5&extra=

其实答案46楼会员pontifex 早就给出来了，只是觉得这么快有答案就不好玩了，因此暂时删除了答案，让大家继续玩，呵呵 吴乐一下，重在参与！

下周题目小黑相关，下次会比较简单点！


本周五题目：房子3个，都要通上水，电，气。但是水电气的线不允许交叉，一个交叉都不行，在平面图上将三个房子通过连线都通上水，电，气。大家可以自己拿张纸拿根笔自己画画。水，电，气的线可以随便绕，只要不交叉就可以，线不能穿过房子，不能穿过水 电 气！

规则：第一个给出准确答案的将获得博扬新思提供的奖品，奖品与每周五拍卖活动可以同时拥有,因为题目比较难所以截至日期07.09.15晚上12：00

未命名.jpg





奖品：


贝尔金时尚小鹰 ￥50元促销订购 一个
------------------------------------
如果随购买新机器一起领奖那么再奖

新到推荐超值悍将礼包￥175元订购 一个
------------------------------------------

下周五题目：小黑相关，奖品届时公布为准！

图片附件: 未命名.jpg (2007-9-7 00:01, 24.74 KB) / 下载次数 924
http://115.28.246.150:8989/attachment.php?aid=16878&k=ddfe526a732454af4962cc736d723ae4&t=1732379408&sid=68FeLl

作者: d-x-s    时间: 2007-9-6 11:20

沙发
作者: d-x-s    时间: 2007-9-6 11:22

明天晚上要去旅游了,没时间了
作者: zhangeddie_07    时间: 2007-9-6 11:27

又不盖了？砖都准备好了
作者: victor_1001    时间: 2007-9-6 12:59

原帖由 zhangeddie_07 于 2007-9-6 11:27 发表
又不盖了？砖都准备好了

拿砖拍老吴！
作者: azuremac    时间: 2007-9-6 23:57

我靠，这不是专门给我准备的么，正准备购新机呢
作者: dv2d4admin    时间: 2007-9-7 09:28

这个题有难度吧
作者: d-x-s    时间: 2007-9-7 09:47

我画出来了,太容易了
作者: d-x-s    时间: 2007-9-7 09:47

怎么在电闹上画?
作者: dv2d4admin    时间: 2007-9-7 09:52

原帖由 d-x-s 于 2007-9-7 09:47 发表
我画出来了,太容易了

靠 开玩笑 那那么容易

想在电脑上画 打开画图保存 然后发上论坛来看看
作者: d-x-s    时间: 2007-9-7 09:58

小儿子在跟前,不让我画,让我带他上街玩
作者: 博扬新思    时间: 2007-9-7 10:05

原帖由 d-x-s 于 2007-9-7 09:58 发表
小儿子在跟前,不让我画,让我带他上街玩

看来不是一个儿子
作者: d-x-s    时间: 2007-9-7 10:11

原帖由 博扬新思 于 2007-9-7 10:05 发表

看来不是一个儿子

我两个儿子
作者: porlarbear    时间: 2007-9-7 10:43

确实比较难搞啊
作者: cfz    时间: 2007-9-7 10:59

晕，，，好玩好玩
作者: dv2d4admin    时间: 2007-9-7 11:47

估计今天是没有人能连起来了
作者: Along_99    时间: 2007-9-7 11:51

那个flash是有bug的，数学方法有解么？
作者: willfcareer    时间: 2007-9-7 12:05

偶来看看吧，哦哦
作者: sgwf007    时间: 2007-9-7 12:07

唉，搞错了，也没画出来

[ 本帖最后由 sgwf007 于 2007-9-7 12:17 编辑 ]

图片附件: 20070907_b9d1518e5329e7fa1b8da2v3V57IrDR7.jpg (2007-9-7 12:07, 46.23 KB) / 下载次数 739
http://115.28.246.150:8989/attachment.php?aid=16885&k=0ff14a559d03852ac8147133fea6b199&t=1732379408&sid=68FeLl

作者: d-x-s    时间: 2007-9-7 12:08

原帖由 dv2d4admin 于 2007-9-7 11:47 发表
估计今天是没有人能连起来了

我看错了 ,没画出来
作者: pontifex    时间: 2007-9-7 12:13     标题: 回复 #1 dv2d4admin 的帖子

如果线可以穿过房子的话，很简单，谁都能做出来；如果不可以，那用数学方法可证明这个题是做不出来的，就不用白费力气了。
作者: fox21cn    时间: 2007-9-7 12:13

sgwf007 画错了
作者: dv2d4admin    时间: 2007-9-7 12:15

原帖由 sgwf007 于 2007-9-7 12:07 发表
老吴看看我这样对不
16885

最左边房子没有通上气 反而接了2个电
作者: sgwf007    时间: 2007-9-7 12:19

我有点搞错了，等我吃完饭再改改
作者: willfcareer    时间: 2007-9-7 12:26

哦，我画出来喽
作者: dv2d4admin    时间: 2007-9-7 12:28

原帖由 pontifex 于 2007-9-7 12:13 发表
如果线可以穿过房子的话，很简单，谁都能做出来；如果不可以，那用数学方法可证明这个题是做不出来的，就不用白费力气了。

这个题是国外的 五星难度 绝对不是死题
作者: pontifex    时间: 2007-9-7 12:32     标题: 回复 #23 dv2d4admin 的帖子

我给一个浅显一点的证明吧：拿出纸笔画一下．
把房子进行编号，叫做1,2,3；而水，电，气分别用A,B,C代替．
首先，只考虑1,2,A,B.可知这四个元素必然会连成一个封闭环．(1-A-2-B).这个环有四条边．

现在把C放到图中去，注意到C必须和1,2都有连接，不管把C放在刚才画出的那个环的外面还是里面，整个平面都会被两个环分成三个互不相通的区域．同时，这两个环必然有两条边是公用的．

现在我们把3放进来，注意：3必须和A,B,C都有连接，这时你会发现，不论把3放在那个区域，总有一个字母和3不能直接相连．
作者: pontifex    时间: 2007-9-7 12:38     标题: 回复 #27 pontifex 的帖子

所以呢，只能把水管先通到一个房子，再从这个房子把水管引出来........
照这样办理，就简单解决了．
作者: Along_99    时间: 2007-9-7 12:42

老吴既然说有答案，我就等着答案公布的日子看看答案就行了，题想了一个上午，没有结论。
作者: d-x-s    时间: 2007-9-7 12:45

原帖由 dv2d4admin 于 2007-9-7 12:28 发表

这个题是国外的 五星难度 绝对不是死题

谁会数学编程?再试试
作者: pontifex    时间: 2007-9-7 12:51     标题: 所以，答案是这样的。

看附件中的图片。

图片附件: 1.JPG (2007-9-7 12:51, 17.34 KB) / 下载次数 644
http://115.28.246.150:8989/attachment.php?aid=16886&k=949218b3bf9f23669990d4c78aa81f13&t=1732379408&sid=68FeLl

作者: pontifex    时间: 2007-9-7 12:54     标题: 回复 #31 pontifex 的帖子

上面的分别是水，电，气；下面是三栋房子。
作者: andrewy    时间: 2007-9-7 12:55

要是楼上这样接谁都会。问题是 每个点都要有3根线的。而且不能串联。
作者: 715208    时间: 2007-9-7 12:55

原帖由 pontifex 于 2007-9-7 12:51 发表
看附件中的图片。

如果是这样也太简单了吧
作者: dv2d4admin    时间: 2007-9-7 12:55

原帖由 pontifex 于 2007-9-7 12:51 发表
看附件中的图片。

肯定是不对的
作者: 715208    时间: 2007-9-7 12:57

老吴来点提示啊。。。。
作者: sgwf007    时间: 2007-9-7 12:57

老吴，一条线分两头算不算交叉

[ 本帖最后由 d-x-s 于 2007-9-7 13:01 编辑 ]
作者: dv2d4admin    时间: 2007-9-7 12:59

原帖由 sgwf007 于 2007-9-7 12:57 发表
老吴，一条线分两头算不算交叉

问题是没有分两头的必要
作者: pontifex    时间: 2007-9-7 12:59

那如果是这样的话，只有用一条线分两头之类的办法了，直接连肯定是不行的，参看我的证明。
作者: pontifex    时间: 2007-9-7 13:01

老吴的题又说是平面的，弄到三维也是不可以的，呵呵。
作者: d-x-s    时间: 2007-9-7 13:02

原帖由 sgwf007 于 2007-9-7 12:57 发表
老吴，一条线分两头算不算交叉

我看可以
作者: coolonion    时间: 2007-9-7 13:05

这题真的有解？我想了半天了……
作者: coolonion    时间: 2007-9-7 13:05

原帖由 pontifex 于 2007-9-7 12:51 发表
看附件中的图片。


不要用常规的思维，那样是不可能解出来的
作者: lstk    时间: 2007-9-7 13:11

等周末回家去画。
作者: 715208    时间: 2007-9-7 13:12

原帖由 lstk 于 2007-9-7 13:11 发表
等周末回家去画。

哼哼哼，等你回家画我就画出来喽
作者: pontifex    时间: 2007-9-7 13:15

老吴还卖关子！我看不下去了！

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:

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
这个视频显示了用作弊的方法解出了这道题。
作者: andrewy    时间: 2007-9-7 13:18

哈哈 。。。。。。。。。。。。。

[ 本帖最后由 andrewy 于 2007-9-7 13:26 编辑 ]
作者: 715208    时间: 2007-9-7 13:23

我晕 真没解啊。。。。
作者: andrewy    时间: 2007-9-7 13:26

:lol
作者: 715208    时间: 2007-9-7 13:26

为什么把没解的答案删除了？
作者: sgwf007    时间: 2007-9-7 13:47

应该可以饶很多圈就可以解，不过没有力气去搞了，放弃了！
作者: dv2d4admin    时间: 2007-9-7 13:57

原帖由 715208 于 2007-9-7 13:26 发表
为什么把没解的答案删除了？

如果是死题不可能那么多人研究，网上还有一个研究这个的坛子，在台湾


这个是要画圈子，通过圈子走的

连接每一个都没有直线
作者: d-x-s    时间: 2007-9-7 14:04

原帖由 dv2d4admin 于 2007-9-7 13:57 发表

如果是死题不可能那么多人研究，网上还有一个研究这个的坛子，在台湾


这个是要画圈子，通过圈子走的

连接每一个都没有直线

平面好象没解,环面??????
作者: 715208    时间: 2007-9-7 14:05

哈哈哈 投机取巧一回。。。。。

图片附件: 未命名.jpg (2007-9-7 14:05, 38.53 KB) / 下载次数 638
http://115.28.246.150:8989/attachment.php?aid=16888&k=aa22e335a625671d64f7193fa4f61cac&t=1732379408&sid=68FeLl

作者: 715208    时间: 2007-9-7 14:06

妈呀 我画的怎么那么难看啊
作者: d-x-s    时间: 2007-9-7 14:07

原帖由 715208 于 2007-9-7 14:05 发表
哈哈哈 投机取巧一回。。。。。

不行吧,这样这道题就没意思了
作者: dv2d4admin    时间: 2007-9-7 14:09

原帖由 715208 于 2007-9-7 14:05 发表
哈哈哈 投机取巧一回。。。。。


图片附件: 20070907_ee6826374cd7ede3a961fiATNOa8b82N.jpg (2007-9-7 14:09, 51.59 KB) / 下载次数 626
http://115.28.246.150:8989/attachment.php?aid=16889&k=7a26759ab5ffcf85656f9d312abec9cc&t=1732379408&sid=68FeLl

作者: 715208    时间: 2007-9-7 14:11

这大红叉子。。。。。想起上学考试不及格的事了
作者: porlarbear    时间: 2007-9-7 14:12

哈哈，lw的红叉子打得爽啊
作者: 715208    时间: 2007-9-7 14:20

为什么只有我的有红叉子。。其他人的没有啊。。。。叉子还特大
作者: sail0828    时间: 2007-9-7 14:21

LW的那个叉子太打击自信心了~~~
作者: sccsccscc    时间: 2007-9-7 17:27

看看~~~~~~~~~~~

[ 本帖最后由 sccsccscc 于 2007-9-7 17:31 编辑 ]

图片附件: 20070907_b9d1518e5329e7fa1b8da2v3V57IrDR7.jpg (2007-9-7 17:27, 41.48 KB) / 下载次数 651
http://115.28.246.150:8989/attachment.php?aid=16891&k=d6b827999d4dfb4fefd5651c9cd56310&t=1732379408&sid=68FeLl

作者: dv2d4admin    时间: 2007-9-7 17:40

原帖由 sccsccscc 于 2007-9-7 17:27 发表
看看~~~~~~~~~~~


图片附件: 20070907_4fcda5280fcaa718a46fg1EWhlvNiAbO.jpg (2007-9-7 17:40, 50.49 KB) / 下载次数 763
http://115.28.246.150:8989/attachment.php?aid=16892&k=bbe5bb1833db39781c09ef0d576e1022&t=1732379408&sid=68FeLl

作者: porlarbear    时间: 2007-9-7 17:40

楼上的不对啊，中间的房子没有气啊
作者: porlarbear    时间: 2007-9-7 17:41

哈哈，又一个大大的红叉子
作者: sccsccscc    时间: 2007-9-7 17:51

现实太残酷了~~~~~~~~

5555555555555555555
作者: I小B黑M    时间: 2007-9-7 18:09

实在是难啊~老吴，你其实也不会吧~哈~！
作者: robyfag    时间: 2007-9-7 18:22

我都关注一天！自己没画出来！
作者: fox21cn    时间: 2007-9-7 18:27

老吴想出来的题目就是难
作者: fox21cn    时间: 2007-9-7 18:28

我也关注一天了，都没有答案呢
作者: lzj198363    时间: 2007-9-7 20:05

果然有难度，但是没答案的主要原因是奖品太弱
俗话说 重赏之下必有勇夫，相信如果奖品是一台T61，答案将在一个小时内出现
作者: 电火    时间: 2007-9-7 20:36

难~~~~~~~~~~
画了半个小时， 没画出来~~~~~~~
看来这期奖品是发不出去了~~~(不如便宜我了)
作者: weizifu    时间: 2007-9-7 20:47

费了几张纸了，绕了N个圈圈
作者: dtx66    时间: 2007-9-7 21:13

之前去lw那里大哥问我这个，当时还想不会特别难，不过。。。。。。
可不可以向3d方向发展，那样有多少管子也能连了- -
作者: ibmfish    时间: 2007-9-7 22:24

老吴，我上图

[ 本帖最后由 ibmfish 于 2007-9-7 22:27 编辑 ]

图片附件: 未命名.JPG (2007-9-7 22:24, 33.46 KB) / 下载次数 633
http://115.28.246.150:8989/attachment.php?aid=16899&k=14ecefdb15902cfde3537a7f143c9611&t=1732379408&sid=68FeLl

作者: ibmfish    时间: 2007-9-7 22:24

不知道对不，限制的条件看得不是很明白。
1、（满足）房子3个，都要通上水，电，气。
2、（满足）但是水电气的线不允许交叉，一个交叉都不行，在平面图上将三个房子通过连线都通上水，电，气。
3、（满足）水，电，气的线可以随便绕，只要不交叉就可以，
4、（满足）线不能穿过房子，不能穿过水 电 气！

[ 本帖最后由 ibmfish 于 2007-9-7 22:26 编辑 ]
作者: weizifu    时间: 2007-9-7 22:31

线不能穿过房子，不能穿过水 电 气！
没有满足
作者: 毒行虎    时间: 2007-9-7 22:37

老吴搞活动。其实是要征求答案吧。

国外活动奖品厚重·~~~
作者: weizifu    时间: 2007-9-7 22:39

原帖由 毒行虎 于 2007-9-7 22:37 发表
老吴搞活动。其实是要征求答案吧。

国外活动奖品厚重·~~~

;P ;P ;P ;P ;P
LW的阴谋一眼就被你识破了
作者: 电火    时间: 2007-9-7 23:06

等LW的答案~~~~~~~~~~~~~~
作者: 毒行虎    时间: 2007-9-7 23:20


作者: coolonion    时间: 2007-9-8 01:56

我想知道奖品是什么？也许能让我有继续研究下去的勇气……
作者: movil    时间: 2007-9-8 02:21

等明天早上 我想一下
作者: havy    时间: 2007-9-8 07:53

应该不是很难！！！！！！！！！！！
作者: fox21cn    时间: 2007-9-8 09:52

还有人解答出答案啊？好期待啊，反正我是做不出来了
作者: weizifu    时间: 2007-9-8 11:48

怎么还没有答案出来。。。
作者: Along_99    时间: 2007-9-8 14:48

原帖由 dv2d4admin 于 2007-9-7 13:57 发表

如果是死题不可能那么多人研究，网上还有一个研究这个的坛子，在台湾


这个是要画圈子，通过圈子走的

连接每一个都没有直线

lw，是不是跟圈子没有关系？你可以通过改变房子的位置简化绕的圈子……
作者: 天地遥昭    时间: 2007-9-8 16:30

。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
作者: dv2d4admin    时间: 2007-9-8 18:50

原帖由 毒行虎 于 2007-9-7 23:20 发表

http://dongxingstone.com/a.gif

房子位置不对 另外还有交叉
作者: jason00fa    时间: 2007-9-8 20:22

老吴是天才！给个无解的题目！
作者: john9854    时间: 2007-9-8 23:02

原帖由 pontifex 于 2007-9-7 12:32 发表
我给一个浅显一点的证明吧：拿出纸笔画一下．
把房子进行编号，叫做1,2,3；而水，电，气分别用A,B,C代替．
首先，只考虑1,2,A,B.可知这四个元素必然会连成一个封闭环．(1-A-2-B).这个环有四条边．

现在把C ...

欧拉公式~~~

如果可以在平面画立体图???
作者: caily    时间: 2007-9-9 08:25

不是我这人直肠子，为得一个鼠标，出那么难的题，老吴你也太抠了。如果我这个答案有效的话，就把鼠标送我女朋友吧，我在剑桥先谢谢您了。嘎嘎嘎嘎
Dudeney.jpg      
这道题是英国最有名的谜题专家Henry Ernest Dudeney创作的，如果想要通过常规的解法，根本不可能。我在网上查了很多资料，通过jordan的双线理论和欧拉定理都可以很容易的证明在同一平面内不能建立所有的有效链接。后面的有两个理论的证明资料。原版的题目叫Oil,Water and Gas Puzzle,我现在在英国留学，我问过了，另外的名字叫Three utilities and Three horses.非常非常有名的谜题。下面的原题，和lw的差不多，不过更直观        


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不可以穿过房子，所以，下面的这个版本的答案就孕育而生了：

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:

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 编辑 ]

图片附件: Dudeney.jpg (2007-9-9 08:36, 1.31 KB) / 下载次数 652
http://115.28.246.150:8989/attachment.php?aid=16904&k=188d1a81852134fce691e20880abb23e&t=1732379408&sid=68FeLl

作者: caily    时间: 2007-9-9 08:58

不行了，我坚持不住了，我先睡觉了，这边都夜里2点了。
作者: 蓝色快车    时间: 2007-9-9 10:50

原帖由 caily 于 2007-9-9 08:25 发表
不是我这人直肠子，为得一个鼠标，出那么难的题，老吴你也太抠了。如果我这个答案有效的话，就把鼠标送我女朋友吧，我在剑桥先谢谢您了。嘎嘎嘎嘎
16904     
这道题是英国最有名的谜题专家Henry Ernest Dud ...



为了一个鼠标？要这样解答？


我有这个本事造飞船牌去了


抗议！！！强烈抗议！！！
作者: madman    时间: 2007-9-9 11:43

………………此题具有很大的厚黑性~请各位切勿钻牛角
作者: dv2d4admin    时间: 2007-9-9 11:44

原帖由 caily 于 2007-9-9 08:25 发表
不是我这人直肠子，为得一个鼠标，出那么难的题，老吴你也太抠了。如果我这个答案有效的话，就把鼠标送我女朋友吧，我在剑桥先谢谢您了。嘎嘎嘎嘎
16904     
这道题是英国最有名的谜题专家Henry Ernest Dud ...

呵呵 重在参与嘛
作者: thinkworld    时间: 2007-9-9 11:54

原帖由 pontifex 于 2007-9-7 13:15 发表
老吴还卖关子！我看不下去了！

1。http://www.supuzzle.com/supuzzle.html
这是题目的出处，是flash格式，可以在线玩。大家可以在线去玩玩！

2。http://mathforum.org/dr.math/faq/faq.3utilities.html
...


这哥们是潜水王啊，05年的ID
作者: caily    时间: 2007-9-9 12:05

难道我的答案还是不行？？
作者: dv2d4admin    时间: 2007-9-9 12:06

原帖由 caily 于 2007-9-9 12:05 发表
难道我的答案还是不行？？

你答案可以

但是你不是第一个人
作者: caily    时间: 2007-9-9 12:08

晕死，真不知道怎么想的，有人有答案了却不说，害我啊，7个小时的时差啊



欢迎光临 鸿利在线|北京Thinkpad水货|IBM水货|Thinkpad笔记本|Thinkpad全球购|Thinkpad美行|Thinkpad水货笔记本|Thinkpad港行笔记本|Thinkpad T14|X13|P15|P17|P1隐士| X1 Carbon 9代 |T14S|2021款X1 Carbon|X1 隐士|Thinkpad非官方论坛|Thinkpad工作站|Thinkpad笔记本论坛|Thinkpad水货 (http://115.28.246.150:8989/) Powered by Discuz! 7.2