Re: [非關] 邏輯數學獵人請進，難題第二發
剛發現證明有問題，重證一次
假設不能畫在空格上，則可以用漢米爾頓路徑證明
漢米爾頓路徑:一路徑(起點不等於終點)經過每一個點恰一次
將題目轉成點和邊，變成
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
推
06/12 01:44, , 1F
06/12 01:44, 1F
推
06/12 10:21, , 2F
06/12 10:21, 2F
→
06/12 10:21, , 3F
06/12 10:21, 3F
→
06/12 10:42, , 4F
06/12 10:42, 4F
推
06/12 17:15, , 5F
06/12 17:15, 5F
→
06/12 17:41, , 6F
06/12 17:41, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 5 篇)：