http://i.imgur.com/xXdZdi6.jpg
想問這題，一開始A的基數小於等於3就不懂了

因為4以上鴿籠不成立證明3以下必定有相同元素和就等於不是所有非空子集都有唯一元素和3以下就只有{ 1 } ~ { 7, 8, 9 } 最多24個sum但有25種subset

先了解題目在幹嘛 每個非空子集合都會有一個元素和元素和的值域落在(1+2+3+4+5)~(9+8+7+6+5)把非空子集合的個數想像成鴿子，元素和值域想成籠子那只要證明值域的範圍小於非空子集合個數(31)就可以用鴿籠證明一定有兩個非空子集合元素和一樣詳解的證法樓上講的很清楚了 就不贅述不過其實也不是4以上不成立啦也能直接用5個元素的情況來證 只是會麻煩一點

https://i.imgur.com/e9ZCsoV.jpg類似題，但籠>鴿直接鴿籠不一定會保證兩個一樣A<=6(藍色)要找兩個一樣但沒辦法保證找到，我們縮小範圍去A<=5(紅色)找，如果找得到代表藍色也有兩個一樣你這題就是A<=5找不到去A<=4找還是找不到就去A<=3

謝謝各位，我研究一下

熊熊發現上面打錯...子集合的元素合值域是落在1~(9+8+7+6+5)才對...有誤導的話非常抱歉qq