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

看板Grad-ProbAsk作者 (憤怒的肥宅)時間8年前 (2017/03/08 23:27), 編輯推噓1(1推 0噓 12→)
留言13則, 3人參與, 最新討論串1/1
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
推
03/09 01:10, , 1F
triangular number
03/09 01:10, 1F
→
03/09 01:19, , 2F
n個箱子最少球數能使每個箱子球數不一樣的worst case
03/09 01:19, 2F
→
03/09 01:19, , 3F
就是0號箱裝0顆 1號箱裝1顆 2號箱裝2顆 … n-1號箱子裝
03/09 01:19, 3F
→
03/09 01:19, , 4F
n-1顆共0+1+2+…+n=(n * (n-1)) / 2顆
03/09 01:19, 4F
→
03/09 01:19, , 5F
若小於這個數量的總球數 必有兩個箱子球數相同
03/09 01:19, 5F
→
03/09 01:21, , 6F
好像不夠嚴謹 有待高手回答
03/09 01:21, 6F
→
03/09 09:48, , 7F
不確定是不是很冗: 先看n(n-1)/2和n的大小關係 畫圖發現n>=3
03/09 09:48, 7F
→
03/09 09:48, , 8F
時前式比較大 然後討論。n=1時和題目不符；n=2時m=0，兩箱
03/09 09:48, 8F
→
03/09 09:48, , 9F
都0；n>=3時討論n、m 、n(n-1)/2關係
03/09 09:48, 9F
→
03/09 09:53, , 10F
如果m比n小 簡單發現一定至少會有兩箱一樣 ；如果m在兩者之
03/09 09:53, 10F
→
03/09 09:53, , 11F
間 那要讓每箱都有球又每箱不同數量m最少要1+2+...+n=n(n+1)
03/09 09:53, 11F
→
03/09 09:53, , 12F
/2 -> 矛盾
03/09 09:53, 12F
→
03/12 18:15, , 13F
感謝樓上兩位大大 結果好像不用鴿籠就做出了了
03/12 18:15, 13F
‣ 更多 wsp50317 的文章
文章代碼(AID): #1Om2BfKd (Grad-ProbAsk)