http://i.imgur.com/ygemh8o.jpg
有大大知道第三題要怎麼證明嗎QQ
明明知道是鴿籠原理 但是不知道怎麼推到有box會有相同兩物
麻煩各位大大了

triangular numbern個箱子最少球數能使每個箱子球數不一樣的worst case就是0號箱裝0顆 1號箱裝1顆 2號箱裝2顆 … n-1號箱子裝n-1顆共0+1+2+…+n=(n * (n-1)) / 2顆若小於這個數量的總球數 必有兩個箱子球數相同好像不夠嚴謹 有待高手回答

不確定是不是很冗: 先看n(n-1)/2和n的大小關係 畫圖發現n>=3時前式比較大 然後討論。n=1時和題目不符；n=2時m=0，兩箱都0；n>=3時討論n、m 、n(n-1)/2關係如果m比n小 簡單發現一定至少會有兩箱一樣 ；如果m在兩者之間 那要讓每箱都有球又每箱不同數量m最少要1+2+...+n=n(n+1)/2 -> 矛盾

感謝樓上兩位大大 結果好像不用鴿籠就做出了了