推 netsphere : 謝謝X大，我研究看看 10/15 14:39
推 keroro321 : 這也可 去掉A及空集,子集數目 64-2 > 14+..+10 =60 10/16 00:11
推 shingai : 問個小問題 想請教xii大不考慮五元素的原因..? 10/19 21:50
※ 引述《netsphere (Ruby&Waku)》之銘言：
: 最近在複習離散數學，看到書中鴿籠原理的ㄧ題
: Let A be a set of six positive integers each of which is less
: than 15. Show that there must be two distinct subsets of A
: whose elements when added up give the same sum.
: 題意看不是很懂，想請教這題意和證法。
在1~14中,選6個相異整數形成集合A
則A必有兩個相異子集其元素總和相等
pf.
在A的子集中,有2或3或4個元素的子集有C(6,2)+C(6,3)+C(6,4)=50個
這些子集的元素和的範圍為(1+2)~(14+13+12+11),即3~50,共48種可能
故必有2個子集其元素總和相等
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.115.31.174
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1413354968.A.71C.html