Re: [理工] 離散 101台大電機
※ 引述《TNC (code)》之銘言：
: 題目如下
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/101/101410.pdf
: 請問
: 5.這題要怎麼證出兩個3角形，第一三角形我是用6人認識不認識的概念
: 請問第二個鴿籠在哪裡呢?
我一樣先從認識不認識的概念分組討論
首先假設六個點分別是A,B,C,D,E,F
因為與A相連的有B,C,D,E,F五個點
故AB,AC,AD,AE,AF這五條邊中必有三條以上的邊同色
不失一般性假設AB,AC,AD皆為紅色
接著討論B,C,D中兩兩鄰邊著色
(1)若BC,BD,CD任兩邊以上為紅邊
因為AB,AC,AD已皆為紅邊,故必存在兩個以上純色三角形(紅)
(2)若三邊皆藍,即BC,BD,CD皆為藍色邊
則BCD為第一純色三角形(藍)
接著討論A,E,F著色情形,
若AE為紅邊,則因為AB已是紅邊,故若BE為紅邊則出現第二純色三角形ABE(紅),
又因為AC已是紅邊,故若CE為紅邊則出現第二純色三角形ACE(紅),
若BE與CE皆為藍邊,則出現第二純色三角形BCE(藍)
若AF為紅邊則同AE為紅邊討論,必出現第二純色三角形
若AE與AF皆為藍邊,則若EF為藍邊就出現第二純色三角形(藍),
若EF為紅邊,則(BE,BF),(CE,CF),(DE,DF)這三組內的兩邊不可皆為紅邊,
否則即出現三角形(紅),若這三組中每組都有至少一邊為藍邊,
則可知E,F中必有一點連接B,C,D這三點其中兩點以上為藍邊,
又BCD已為藍色三角形,故必出現第二純色三角形(藍)
(3)若有2藍邊1紅邊,不失一般性設BC為紅,BD與CD為藍邊
則ABC為第一純色三角形(紅)
接著類似(1)之討論A,E,F著色情形,
若AE為紅邊,則因為AB已是紅邊,故若BE為紅邊則出現第二純色三角形ABE(紅),
又因為AD已是紅邊,故若DE為紅邊則出現第二純色三角形ACE(紅),
若BE與DE皆為藍邊,則出現第二純色三角形BDE(藍)
若AF為紅邊則同AE為紅邊討論,必出現第二純色三角形
若AE與AF皆為藍邊,則若EF為藍邊就出現第二純色三角形(藍),
若EF為紅邊,若BE,BF皆為紅邊,則BEF為第二純色三角形(紅),
若CE,CF皆為紅邊,則CEF為第二純色三角形(紅),
若BF,CF皆為紅邊,則BCF為第二純色三角形(紅),
若BE,CE皆為紅邊,則BCE為第二純色三角形(紅),
剩下以下兩種情形:BE,CF皆藍邊或BF,CE皆藍邊
不失一般性設BF,CE皆為藍邊,
則若DF為藍邊 => BDF為第二純色三角形(藍)
若DE為藍邊 => CDE為第二純色三角形(藍)
若DF,DE皆紅邊=> DEF為第二純色三角形(紅)
由以上(1)(2)(3)之討論可知
無論如何著色,必出現兩個以上的純色三角形.
雖然討論看起來很繁雜,不過其實(2)(3)討論方法差不多,幾乎複製貼上而已.
我覺得可能有更好的作法,
不過在還沒出現更好的作法之前,暫時先提供你一個可以證的方法
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.220.207
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：