推 TNC:所以題目應該是 proper subset嗎? 10/13 22:56
推 wheels:黃子嘉離散課本2-85例61，同題目，不過是中文XD 10/13 23:05
推 showyoulovex:感謝解惑 謝謝 10/14 03:25
※ 引述《kkilljeff (幻夜)》之銘言：
: ※ 引述《showyoulovex (NONO)》之銘言：
: : 第一題(97中央):http://ppt.cc/D%28PB
: : 答案:
: : 2的8次方-1=255 <-子集各數
: : sum最小=2 最大為2+3.......+17+19=77
: : 根據鴿籠 (255/77)取上界=4
: : 我不懂的點在於:為什麼是子集各數除以sum最大
: : ---------------------------
: : 有人可以分享一下概念嗎 感謝
: 子集個數有255個 而sum的值範圍是2~77 為整數
: 而255個子集的sum分佈在整數2~77
: 最好的情況下 255/76=3.xxx
: 因此一定會有4個子集的sum分佈在同一個整數上
: : 第二題:
: : 題目:S為6個正整數集合,其中最大值為14
: : 證明S的非空子集元素和皆不相同
: : 第二題 我不懂怎麼去解，還請各位高手為小弟解惑 感恩~
: 第二題想不出來 求高手解惑
: 可是假設S={2,3,5,7,11,14}
: 那S的子集有A={2,3} B={5}
: S假設並沒有跟題目矛盾 可是子集的元素和會相同
: 是題目有誤還是我哪裡想錯了??
我想應該是原PO的題目打錯了 這題應該是某年逢甲的題目
題目是要證S的所有非空子集的元素和不可能皆不同
如果用最直接的來看 S的非空子集有2^6 - 1 = 63
元素和的範圍是 1 到 (9+10+11+12+13+14) => 1~69 => 69種
所以這個方法行不通
但是非空子集也可以只包含1/2/3/4/5個元素
現在考慮最多包含5個元素的非空子集
子集數: C(6,1) + C(6,2) + C(6,3) + C(6,4) + C(6,5) = 2^6 - C(6,0) - C(6,6)
= 62
元素和的範圍是 1 到 (14+13+12+11+10) => 1~60 => 60種
因此必有兩個子集有相同的元素和
--
※ 發信站 :批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186