試證

來源: 2023-09-01 05:35:45 [博客] [舊帖] [給我悄悄話] 本文已被閱讀:

把9個專家化為平麵上的9個點,且無3點共線,如果某兩位專家可以用同一語言交流(多於一種語言的隻算其中一種),就在這兩點間連一條某一顏色的線段(代表某一語言)。反證法:顯然從一點出發最多連3條不同顏色的線,否則至少有兩條線顏色相同,這兩條顏色相同的線所在的3個點所代表的3個專家可以說同一種語言。所以9個點最多連[9*3/2]=13根線。如果其中一點A,可連3條不同顏色的線段到B,C,D, 又B,C,D之間又至少存在一條線,其與A出發的3條線段顏色各不相同,否則可以形成3條邊顏色相同的三角形(題被證)。所以ABCD4點之間至少存在4條不同顏色的線段。A和剩下的5個沒有連線,但和其中任何兩點所形成的三角形中至少有兩點相連,即A的對邊,共有C(5,2)=10條,即9個點至少有10+4=14條線段相連, 矛盾。如果A隻能連2條,1條,0條,那麽A和剩下的點能得到更多的連線。