Re: [理工] 離散 101台大電機
※ 引述《TNC (code)》之銘言：
: 題目如下
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/101/101410.pdf
: 請問
: 5.這題要怎麼證出兩個3角形，第一三角形我是用6人認識不認識的概念
: 請問第二個鴿籠在哪裡呢?
我不知道這題能不能鴿籠，以下提供一個非鴿籠的double counting作法
假設 Vertex set 為{1, 2, ..., 6}
令 r_i 代表每個點所連到的紅邊數 i=1~6
Claim: K_6 中同色三角形的數量為
6
C(6, 3) - (1/2) * Σ r_i*(5-r_i) ..........(1)
i=1
所有三角形 非同色三角形數
原因是K_6任何一個非同色的三角形，必定有兩個頂點是同時被藍邊及紅邊連到的
如果我們利用 (2 * 非同色三角形數) 去數到底有幾個上面這樣的頂點
而對於任何一個頂點 i 來說，因為degree均為5
所以他一共被數了 r_i * (5-r_i) 這麼多次
紅邊可能性 藍邊可能性
因此得到(1)
另外再由算幾不等式知 r_i(5-r_i) <= (5/2)^2 = 25/4
因此(1) >= 20 - (1/2) * 6 * (25/4) = 20 - 75/4 = 5/4
所以 K_6 中至少有2個同色三角形, QED
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.128.130
→
03/18 22:54, , 1F
03/18 22:54, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：