作者triumphant10 (yu12510 )
看板Grad-ProbAsk
標題[理工] 離散數學的證明題
時間Sun Dec 23 00:28:55 2018
大家好
Let S be a set of n points in the plane such that the distance between any two
is at least one .
Prove that there are at most 3n-3 pairs of points with distance exactly one.
https://imgur.com/a/Z4WyGPV
(附上原始題目)
請問看看有沒有大神可以證的出來或是提供點線索給小弟我
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.7.151
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1545496138.A.44C.html
1F：推 Leaving: 幫推 作業好難都想不到QQ 12/23 00:57
2F：→ Leaving: 目前這題只想到 如果把距離為1的邊都加上去行成一個新圖 12/23 01:03
3F：→ Leaving: 可以證明它是planar graph 12/23 01:03
5F：→ Leaving: 可是就只能證到有3n-6條edge(pair)而已 12/23 01:05
6F：→ Leaving: 不知道3n-3是怎麼來的 12/23 01:06
7F：→ Leaving: 還是這樣就算證明結束了?? 12/23 01:08
8F：推 eggy1018: 這題跟 台大電機104的蠻像的，我看別人的解釋是用畫圓 12/23 01:13
9F：→ eggy1018: 但是這一題多減去3... 12/23 01:14
11F：→ ponponjerry: 我用數學歸納證，有錯請指教 12/23 10:44
12F：→ triumphant10: 原來這裡都是修電機離散的XD 12/23 10:53
13F：→ triumphant10: P大，我也是用數學歸納法去想 12/23 10:53
14F：推 Leaving: 其實我是同時有修課也有要考試啦 12/23 11:09
15F：→ Leaving: p大的歸納法看起來怪怪的 n=k使用的假設和n=k+1證出來的 12/23 11:10
16F：→ Leaving: 好像不一樣 12/23 11:10
17F：推 zqAI3yGOAT: 有人可以說明一下作業第一題的3嗎QQ 12/24 21:50
18F：→ Leaving: 把g1用矩陣表示 可以得到每個點的deg=4 12/24 22:15
19F：→ Leaving: 所以去除4條邊後 c=1 or 2 就能帶公式了 12/24 22:16