Re: [數學]來懂一下吧

[Egriawei (Altimate．Weapon)]

※ 引述《holydc (一將功成萬骨枯)》之銘言：
: ※ 引述《zerorain (try and trust)》之銘言：
: : 今有人數為 n 的一群人 S。S 可分為 A0, A1,…, An-1。
: : 此中 Ai 表示 S 中有 i 個朋友的那些人。視 ai 為鴿，Ai 為籠。
: : 在此 n 鴿 n 籠，鴿籠原理得不出結論，
: : 但稍加注意就可看出 A0 與 An-1 中必有一籠是空的。
: : 若 A0 不空，表示有一人跟其他所有人都不是朋友，
: : 因此沒有一人認識所有其他 n-1 人，此即表示 An-1，是空的；
: : 若 An-1，不空表示有一人認識所有其他 n-1 人，
: : 因此不可能有一人跟其他所有人都不是朋友，
: : 此即表示 A0 是空的。故或 A0 或 An-1 為空，不管如何，
: : S 事實上分為 n-1 類。由鴿籠原理，有一類至少有二人。
: : 換言之，有二人各有一樣多的朋友。
: 請問老師...鴿籠原理是什麽東西呀 ._./
哈哈
我來化嚴謹的證明為簡
簡而言之

"今天假設有n個人來校慶與會"

我們使用反証法
試圖推翻"有二人認識的熟人一樣多"的結論
因此我們儘量讓大家認識的人不一樣多휊討論兩種情形:

(1)分成認識1~n-1個人共n-1組
這是合理的,只認識1個人的人
他所認識的人就是"認識所有人的那個人"
如此填入n個人
必有兩者同類,即認識同多人
(2)分成認識0~n-2個人也是n-1組
不會有人認識她之外全部n-1個人
因為有人不認識任何人士來裝熟的
所以也填入n人
如此必有兩者同類,即認識同多人

綜合(1),(2),與原假設矛盾
所以此n人中必有兩人以上認識的熟人一樣多

--
天下沒有不散的筵席 即使今日我們走向四方
  你是否還記得那 藍天白雲之下的共同回憶
===========================藍天白雲==========================
看著天上星星 我駕著太空船飛行!
潛入到深海底 探尋那神秘的遺跡
在漫天烽火裡 我背著步槍向前進 ...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.98.32
→ flutist1008:你講的我更不懂了@@
※ 編輯: Egriawei        來自: 61.224.98.71         (04/19 21:58)
→ holydc:+1... 我只是不知道鴿籠原理在搞什麼啊!!
→ holydc:零雨大大說的還蠻易懂的