創作內容

0 GP

拉姆齊定理-友誼

作者:Ken│2020-10-24 20:03:02│贊助:0│人氣:20
分享一個很好玩的東西
我覺得這幾乎不太需要甚麼數學背景
因為下面的說明不太需要什麼符號
但是這是一個很難的邏輯問題


假定現在有一場聚會有 n 大於等於 2 個人,並且我們把這群人分成 2 個集合

這兩個集合分別為 R 集合(紅)與 B 集合(藍),且在外面的那一人,他是這兩個集合中的其中一人。
與此人互相認識的人,用紅線拉起來,與他不認識的人用藍線拉起來,若我們有n 個人,即我們總共有 n 個點,若這個點全部都是由藍色跟此人做連結,就代表這場聚會根本沒有人認識他,但是這是不可能的,因為我們是從一群認識他跟不認識他的一群人中抽出,所以”一個點全部都是被藍色線所連接”這樣的情況是不可能成立的。

所以,我們可以知道這個人被 n-1 條線所接(顯而易見的狀況,兩個人構成一條線,但是我們這邊所談論的只一對多而已,其他人有共線的情況我們不必去關心),然後這 n-1 條線裡面至多有 n-2 條藍線。
注意上面提到的狀況是”至多”因為我們不允許有一個人是完全被藍線所接。

最後假定現在任意選取兩點,且這兩點所連接的藍線數目都不一樣,我們有 n個點,並考慮下圖

現在假定有 2 個點,而這兩個人分別代表不同的點 A&B,他們是不同的元素,而這兩個元素都屬於下面這兩個集合的其中一個集合,並允許兩個人可以都在同一個集合裡面或者不在同一個集合裡面。

且我們前面已經證明一 n 個點的集合裡面每個點出發都有 n-1 條線與至多 n-2條藍線,所以其中一個點如果有超過 n-2 條藍線是不可能的,但是如果有 n-3 條另外一個人必定也是 n-3 因為我們談論的是彼此認識或彼此不認識,所以不論如何在至少兩個人以上的聚會中,他們兩個人的紅線跟藍線數目要一樣,亦即他們認識的人數要相同。

由此證明
n>1 個人之中,必有兩個人互相認識的人數是相同的

引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4958899
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 1 篇留言

羽刈
這個的一般情形很難

10-25 07:24

Ken
是啊10-25 11:07
我要留言提醒:您尚未登入,請先登入再留言

喜歡★ad100ad10 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:統計力學(一)...

追蹤私訊

作品資料夾

mirk0409大家
初次接委託><! Q版頭像模板300$NTD! 歡迎來小屋參觀or委託!看更多我要大聲說7小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】