[理工] 95 彰師大 鴿籠原理

[wsp50317 (憤怒的肥宅)]

http://i.imgur.com/ygemh8o.jpg

有大大知道第三題要怎麼證明嗎QQ

明明知道是鴿籠原理 但是不知道怎麼推到有box會有相同兩物

麻煩各位大大了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.254.210.101
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1488986857.A.527.html
推 shownlin: triangular number
→ shownlin: n個箱子最少球數能使每個箱子球數不一樣的worst case
→ shownlin: 就是0號箱裝0顆 1號箱裝1顆 2號箱裝2顆 … n-1號箱子裝
→ shownlin: n-1顆共0+1+2+…+n=(n * (n-1)) / 2顆
→ shownlin: 若小於這個數量的總球數 必有兩個箱子球數相同
→ shownlin: 好像不夠嚴謹 有待高手回答
→ vcyc: 不確定是不是很冗: 先看n(n-1)/2和n的大小關係 畫圖發現n>=3
→ vcyc: 時前式比較大 然後討論。n=1時和題目不符；n=2時m=0，兩箱
→ vcyc: 都0；n>=3時討論n、m 、n(n-1)/2關係
→ vcyc: 如果m比n小 簡單發現一定至少會有兩箱一樣 ；如果m在兩者之
→ vcyc: 間 那要讓每箱都有球又每箱不同數量m最少要1+2+...+n=n(n+1)
→ vcyc: /2 -> 矛盾
→ wsp50317: 感謝樓上兩位大大 結果好像不用鴿籠就做出了了