作者ddtddt (得)
看板puzzle
標題[問題] 八點八邊圖
時間Wed Jul 30 11:42:14 2014
證明或反證
任意給一個八點八邊圖,(規定每個點的degree至少要是一 )
你一定都可以在點中填入三個 1 三個-1 及兩個 0
使得所有邊的左右兩點之積必不為 -1 .(換句話說 1 和 -1不相鄰)
ex:
1 -- 1 0 1 -- 1 --1 -- 0 --(-1)--(-1)
\ / / \ / /
1 -- 0--(-1) 0 -- (-1)
(-1)--(-1)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 14.136.145.87
※ 文章網址: http://webptt.com/m.aspx?n=bbs/puzzle/M.1406691736.A.7C4.html
1F：推 walkwall:嗯...如果是9邊就有K3,3了 8邊似乎是成立 07/30 21:24
2F：→ ddtddt:謝謝捧場推文 沒人討論好可憐@@ 07/30 22:23
3F：→ ddtddt:K3,3很好的點 不過這邊限制八點都至少degree1 07/30 22:24
4F：推 walkwall:喔 抱歉忽略掉degree1的部分 只是沒這條件也似乎成立? 07/30 22:32
5F：→ walkwall:另一個角度來看問題是 : 是不是能保證存在兩個點 去掉之 07/30 22:34
6F：→ walkwall:後 剩餘的連通區域最多三個點? 07/30 22:35
7F：→ ddtddt:沒限制條件也似乎成立沒錯^^ 只是我覺得最難證的是八點 07/30 23:13
8F：→ ddtddt:怎麼拿掉兩點應該是蠻關鍵的,其實我現在沒有漂亮證明 07/30 23:15
9F：→ ddtddt:不過應該不是連通區域最多三點 如果剩 2 2 2的話就不行 07/30 23:19
10F：推 walkwall:嗯 222我是漏掉考慮了 07/30 23:56
11F：→ ddtddt:我目前是有一個蠻長的證明啦:p 想看看大家有沒有更聰明法 07/31 11:44
12F：→ ddtddt:謝謝走牆大 07/31 11:50