[離散] Pigeonhole Principle

離散分類題庫 P136. 86題

Let S be a set of five positive integers the maximum of
which is at most 9, Prove that the sums of the elements
in all the nonempty subsets of S can't all be distinct

解答是考慮1 <=|A|<=3 的時候，證明就ok


可是題目說5個正整數，如果我考慮5個，
則|A| = 2^5 -1 = 31
而 1 <= sum <= 5+6+7+8+9=35
這樣就不能用鴿籠原理了耶~
(3個可以得證，5個不行這樣還算得證嗎?)

請問考試時我怎麼知道要取3個來證明~?


還有他說S集合中有5個正整數，但題目沒有說全相異，
有可能會不同嗎? 還是因為是集合所以一定相異


謝謝