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

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