作者cooper90413 (cooper)
看板Hunter
标题Re: [非关] 逻辑数学猎人请进,难题第二发
时间Tue Jun 12 01:31:05 2012
刚发现证明有问题,重证一次
假设不能画在空格上,则可以用汉米尔顿路径证明
汉米尔顿路径:一路径(起点不等於终点)经过每一个点恰一次
将题目转成点和边,变成
A-B-C D
| | | |
E-F-G-H-I
| | | | |
J-K-L-M-N
| | | | |
O-P-Q-R-S
| | | | |
T-U-V-W-X
共有24个点与37条边
而在汉米尔顿路径中,
1.除起点终点,每个点一定是一进一出(所有点都只有小於等於两条边)
因此某点附近多於两条边的都要砍掉
有3条边的点:B,C,E,H,I,J,N,O,S,U,V,W
有4条边的点:F,G,K,L,M,P,Q,R
而由於避免砍掉边时会影响到其它的点,所以取不相邻的点来砍
B,E,I,O,S,U,W须删掉一条边共7条
G,K,M,Q须删掉两条边共8条
总共至少要删掉15条边
A-
B-C D
| | | |
E-F-
G-H-
I
| | | | |
J-
K-L-
M-N
| | | | |
O-P-
Q-R-
S
| | | | |
T-
U-V-
W-X
2.路径中恰有(24-1)=23条边
因此必须恰砍掉(37-23)=14条边
起点D-I-......-终点 有n个点,路径就有n-1条边
1.2矛盾,故画不出来
※ 引述《cumulonimbus (奶油云)》之铭言:
: 这个问题是我的同事问我的,我那整个礼拜都在想这一题,
: 想到现在半年已过,还是没有解答,所以上来求助。
: 那时候同事跟我说有正确解答,不过我真的想了很久我觉得我被唬烂了。
: 不知道有没有神人可以帮解。
: 题目:「○○○ ○
: ○○○○○
: ○○○○○
: ○○○○○
: ○○○○○」 画一条线经过所有的球,不可交叉,不可斜线。
: 乍看之下我以为非常简单,其实并不然,我真的认真的认为我被唬烂了。
: 只是我不知道有没有甚麽理论可以证明我被唬烂。
: 烦请各位 难题猎人 帮忙解答 谢谢。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.91.176
1F:推 kevinchen127:再推一次XD 06/12 01:44
2F:推 aiweisen:原PO明年要考研究齁~ 06/12 10:21
3F:→ aiweisen: ^所 06/12 10:21
4F:→ cooper90413:去年考的XD,我还特地把之前的笔记翻出来看 06/12 10:42
5F:推 nobrother:是考数学系吗 06/12 17:15
6F:→ cooper90413:资工,这是离散数学图论的部分 06/12 17:41