忘記題號惹
題目:
一個集合S有5個正整數，最大不超過9，證明S的所有子集合(不包含空集合)
的元素和(sum of elements)不會都不同
想問一下這題要怎麼解，是用鴿籠原理嗎?
原本是想說S的非空子集合有2^5 - 1 = 31個
然後從5個數最小1~最大1+6+7+8+9 可是這個還是31個數 不知怎麼算
求大大們開釋

居然考這種基本題@@

我用矛盾證法 但我覺得證的很不嚴謹...

我怎麼想也都是籠子大於鴿子，求神人解答

每數都不同，size1，2，3的子集合有25個

我直接把31的狀況全列出來然後再說6+9=7+8

子集合和範圍在1-25(9+8+7)?說錯1-24

然後又因為31已經是極端值了 所以直接得證任選五個數的合必會重複

http://i.imgur.com/lURMUak.jpg剛剛翻課本 是這種題目吧?

看起來是這樣，當下寫發現大小1，2，3的所有子集合數就大於他們的範圍了

話說為什麼是1+6+7+8+9

56789值域範圍也是31個數 5~3516789 26789 36789 46789 56789同理所以解決這五個 這題鴿籠應該就解決了 不知道我有沒有露了什麼

https://i.imgur.com/59DZ0dC.jpg只有證|S|=5不知道對不對

考慮數字越大越好(和不會在限制內減少選項)有兩個限制1.選到的數同樣的差不能出現3次2.選的數不能為現有的差的和 所以從9,8,7開始 這時候選項只剩下{5,4,3}但要選兩個 一定會選到一個數使得選出來的數列不符合限制 大概是這樣 詳細的太長了

越小越好吧 小的找得到大的一定找得到

這題應該是2^5-1=31 然後無論最小元素和結合的取法或最大元素和集合的取法 他們的Power set下的各個子集合的範圍都會小於31 再根據鴿籠就可以了集合 不是 結合 打錯

這方法真棒 哈哈 倒是沒想到

大概是課本題目 因為題目的說法是只要有任何一組subset sum相同就好 所以可以縮小取的subset大小 然後就用鴿籠了

看到才想起自己看過 倒是忘的乾淨

我是分開討論欸 討論最大是9跟最大是8以下如果最大是8值域一定要小於27如果最大是9則5＋6＋7＋8＋1一定不在值域裡面所以也是小於30

看不懂樓上最大是9後面那句

最大是9，值可能有5+6+7+9呀是可以分組討論:若{6,7,8,9}不是S的子集，sum的範圍是m≦sum < m+6+7+8+9，長度小於31可以直接套鴿籠了m是S中的最小元素若{6,7,8,9}是S的子集，也很容易在m~m+30中剃除一個值

當初是寫1＋6＋7＋8＋1拉說錯了不過我是用廣義的a b c d四個元素 但我好像真的沒考慮到5678看來是錯了QQ

要怎麼剃除一個值

舉例若S={1,6,7,8,9}，則sum不會有 2,3,4,5若S={5,6,7,8,9}，sum不會有10

早知道9還不如給他爆開8以下再用鴿籠就好

爆開了 -12

靠北我忘記我不小心把鴿子跟籠子想返還証得沾沾自喜想說好開心不需要証到第二步把範圍縮小==