作者CYCUStore (中原大學店)
看板Grad-ProbAsk
標題[理工] 108中山離散鴿籠?
時間Sat Feb 2 19:34:18 2019
忘記題號惹
題目:
一個集合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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549107260.A.C0C.html
1F：推 Dora5566: 居然考這種基本題@@ 02/02 19:35
算不出來 慘了..
2F：推 sdfg014025xx: 我用矛盾證法 但我覺得證的很不嚴謹... 02/02 19:36
3F：推 qqgnoe466263: 我怎麼想也都是籠子大於鴿子，求神人解答 02/02 19:37
4F：推 h3882249: 每數都不同，size1，2，3的子集合有25個 02/02 19:43
5F：推 sooge: 我直接把31的狀況全列出來然後再說6+9=7+8 02/02 19:44
6F：→ h3882249: 子集合和範圍在1-25(9+8+7)? 02/02 19:44
7F：→ h3882249: 說錯1-24 02/02 19:45
8F：→ sooge: 然後又因為31已經是極端值了 所以直接得證任選五個數的合 02/02 19:45
9F：→ sooge: 必會重複 02/02 19:45
11F：→ moozkito: 剛剛翻課本 是這種題目吧? 02/02 19:46
懂了...原來課本就有 感謝各位大大
12F：推 h3882249: 看起來是這樣，當下寫發現大小1，2，3的所有子集合數就 02/02 19:50
13F：→ h3882249: 大於他們的範圍了 02/02 19:50
14F：推 ChunagMT: 話說為什麼是1+6+7+8+9 02/02 19:56
想說要湊最小數一定要1 其他就最大數湊最大範圍
其實一開始是用1~5+6+7+8+9 可是大太多了...
※ 編輯: CYCUStore (36.231.173.2), 02/02/2019 20:04:34
15F：→ sooge: 56789值域範圍也是31個數 5~35 02/02 20:05
16F：→ sooge: 16789 26789 36789 46789 56789同理 02/02 20:07
17F：→ sooge: 所以解決這五個 這題鴿籠應該就解決了 不知道我有沒有露了 02/02 20:08
18F：→ sooge: 什麼 02/02 20:08
20F：→ albertnien: 只有證|S|=5不知道對不對 02/02 20:45
21F：→ DLHZ: 考慮數字越大越好(和不會在限制內減少選項)有兩個限制1.選到 02/02 20:47
22F：→ DLHZ: 的數同樣的差不能出現3次2.選的數不能為現有的差的和 所以從 02/02 20:47
23F：→ DLHZ: 9,8,7開始 這時候選項只剩下{5,4,3}但要選兩個 一定會選到一 02/02 20:47
24F：→ DLHZ: 個數使得選出來的數列不符合限制 大概是這樣 詳細的太長了 02/02 20:47
25F：推 skyHuan: 越小越好吧 小的找得到大的一定找得到 02/02 21:40
26F：推 meokay: 這題應該是2^5-1=31 然後無論最小元素和結合的取法或最大 02/02 21:50
27F：→ meokay: 元素和集合的取法 他們的Power set下的各個子集合的範圍 02/02 21:50
28F：→ meokay: 都會小於31 再根據鴿籠就可以了 02/02 21:50
29F：→ meokay: 集合 不是 結合 打錯 02/02 21:51
32F：→ rockieloser: 這方法真棒 哈哈 倒是沒想到 02/02 22:22
33F：推 ruifan: 大概是課本題目 因為題目的說法是只要有任何一組subset su 02/02 22:22
34F：→ ruifan: m相同就好 所以可以縮小取的subset大小 然後就用鴿籠了 02/02 22:22
35F：→ rockieloser: 看到才想起自己看過 倒是忘的乾淨 02/02 22:24
36F：推 nannnnn: 我是分開討論欸 討論最大是9跟最大是8以下如果最大是8值 02/02 22:30
37F：→ nannnnn: 域一定要小於27如果最大是9則5＋6＋7＋8＋1一定不在值域 02/02 22:30
38F：→ nannnnn: 裡面所以也是小於30 02/02 22:30
39F：推 Dora5566: 看不懂樓上最大是9後面那句 02/02 22:41
40F：→ ERT312: 最大是9，值可能有5+6+7+9呀 02/02 22:44
41F：→ ERT312: 是可以分組討論:若{6,7,8,9}不是S的子集，sum的範圍是 02/02 22:48
42F：→ ERT312: m≦sum < m+6+7+8+9，長度小於31可以直接套鴿籠了 02/02 22:49
43F：→ ERT312: m是S中的最小元素 02/02 22:50
44F：→ ERT312: 若{6,7,8,9}是S的子集，也很容易在m~m+30中剃除一個值 02/02 22:51
45F：推 nannnnn: 當初是寫1＋6＋7＋8＋1拉說錯了不過我是用廣義的a b c d 02/02 22:54
46F：→ nannnnn: 四個元素 但我好像真的沒考慮到5678看來是錯了QQ 02/02 22:54
47F：推 Dora5566: 要怎麼剃除一個值 02/02 22:56
48F：→ ERT312: 舉例若S={1,6,7,8,9}，則sum不會有 2,3,4,5 02/02 22:58
49F：→ ERT312: 若S={5,6,7,8,9}，sum不會有10 02/02 22:59
50F：→ nannnnn: 早知道9還不如給他爆開8以下再用鴿籠就好 02/02 23:00
51F：→ q79236: 爆開了 -12 02/02 23:12
52F：推 yunghan15: 靠北我忘記我不小心把鴿子跟籠子想返還証得沾沾自喜想 02/03 09:39
53F：→ yunghan15: 說好開心不需要証到第二步把範圍縮小== 02/03 09:40