[理工] 108中山離散鴿籠?

[CYCUStore (中原大學店)]

忘記題號惹

題目:

一個集合S有5個正整數，最大不超過9，證明S的所有子集合(不包含空集合)

的元素和(sum of elements)不會都不同

想問一下這題要怎麼解，是用鴿籠原理嗎?

原本是想說S的非空子集合有2^5 - 1 = 31個

然後從5個數最小1~最大1+6+7+8+9 可是這個還是31個數 不知怎麼算

求大大們開釋

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.173.2
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549107260.A.C0C.html
推 Dora5566: 居然考這種基本題@@
算不出來 慘了..
推 sdfg014025xx: 我用矛盾證法 但我覺得證的很不嚴謹...
推 qqgnoe466263: 我怎麼想也都是籠子大於鴿子，求神人解答
推 h3882249: 每數都不同，size1，2，3的子集合有25個
推 sooge: 我直接把31的狀況全列出來然後再說6+9=7+8
→ h3882249: 子集合和範圍在1-25(9+8+7)?
→ h3882249: 說錯1-24
→ sooge: 然後又因為31已經是極端值了 所以直接得證任選五個數的合
→ sooge: 必會重複
→ moozkito: http://i.imgur.com/lURMUak.jpg
→ moozkito: 剛剛翻課本 是這種題目吧?
懂了...原來課本就有 感謝各位大大
推 h3882249: 看起來是這樣，當下寫發現大小1，2，3的所有子集合數就
→ h3882249: 大於他們的範圍了
推 ChunagMT: 話說為什麼是1+6+7+8+9
想說要湊最小數一定要1 其他就最大數湊最大範圍
其實一開始是用1~5+6+7+8+9 可是大太多了...
※ 編輯: CYCUStore (36.231.173.2), 02/02/2019 20:04:34
→ sooge: 56789值域範圍也是31個數 5~35
→ sooge: 16789 26789 36789 46789 56789同理
→ sooge: 所以解決這五個 這題鴿籠應該就解決了 不知道我有沒有露了
→ sooge: 什麼
推 albertnien:  https://i.imgur.com/59DZ0dC.jpg
→ albertnien: 只有證|S|=5不知道對不對
→ DLHZ: 考慮數字越大越好(和不會在限制內減少選項)有兩個限制1.選到
→ DLHZ: 的數同樣的差不能出現3次2.選的數不能為現有的差的和 所以從
→ DLHZ: 9,8,7開始 這時候選項只剩下{5,4,3}但要選兩個 一定會選到一
→ DLHZ: 個數使得選出來的數列不符合限制 大概是這樣 詳細的太長了
推 skyHuan: 越小越好吧  小的找得到大的一定找得到
推 meokay: 這題應該是2^5-1=31 然後無論最小元素和結合的取法或最大
→ meokay: 元素和集合的取法 他們的Power set下的各個子集合的範圍
→ meokay: 都會小於31 再根據鴿籠就可以了
→ meokay: 集合 不是 結合 打錯
推 skyHuan: https://i.imgur.com/Rq4A3op.jpg
推 ruifan:  https://i.imgur.com/QFR2Bjt.jpg
→ rockieloser: 這方法真棒 哈哈 倒是沒想到
推 ruifan: 大概是課本題目 因為題目的說法是只要有任何一組subset su
→ ruifan: m相同就好 所以可以縮小取的subset大小 然後就用鴿籠了
→ rockieloser: 看到才想起自己看過 倒是忘的乾淨
推 nannnnn: 我是分開討論欸 討論最大是9跟最大是8以下如果最大是8值
→ nannnnn: 域一定要小於27如果最大是9則5＋6＋7＋8＋1一定不在值域
→ nannnnn: 裡面所以也是小於30
推 Dora5566: 看不懂樓上最大是9後面那句
→ ERT312: 最大是9，值可能有5+6+7+9呀
→ ERT312: 是可以分組討論:若{6,7,8,9}不是S的子集，sum的範圍是
→ ERT312: m≦sum < m+6+7+8+9，長度小於31可以直接套鴿籠了
→ ERT312: m是S中的最小元素
→ ERT312: 若{6,7,8,9}是S的子集，也很容易在m~m+30中剃除一個值
推 nannnnn: 當初是寫1＋6＋7＋8＋1拉說錯了不過我是用廣義的a b c d
→ nannnnn: 四個元素 但我好像真的沒考慮到5678看來是錯了QQ
推 Dora5566: 要怎麼剃除一個值
→ ERT312: 舉例若S={1,6,7,8,9}，則sum不會有 2,3,4,5
→ ERT312: 若S={5,6,7,8,9}，sum不會有10
→ nannnnn: 早知道9還不如給他爆開8以下再用鴿籠就好
→ q79236: 爆開了  -12
推 yunghan15: 靠北我忘記我不小心把鴿子跟籠子想返還証得沾沾自喜想
→ yunghan15: 說好開心不需要証到第二步把範圍縮小==