Re: [理工] [離散] 鴿籠
※ 引述《mqazz1 (無法顯示)》之銘言：
: 假設S為6個正整數的集合，其最大值為14
: 證明S的所有非空子集的元素和不可能皆不同
: 謝謝
Let S' denotes a subset of S and Sum(S') sums the values of elements in S.
1<= Sum(S') <= 14 + 13 + 12 +11 +10 + 9 = 69 ,
and |power set(S)-{}| = 2^6 -1 = 63.
Now it's reasonable for Sum(S').
But if we look at the S' which has at most 5 cardinality.
1<= Sum(S') <= 14 + 13 + 12 +11 +10 +9 =60,
ans |power set(S)-{}-S|=62
It's contradictive for that 62 < 60!!
So, we know it is impossible that any sums of two nonempty subset can be
distinct.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.187.85
※ 編輯: privatewind 來自: 59.126.187.85 (12/19 17:30)
※ 編輯: privatewind 來自: 59.126.187.85 (12/19 17:31)
推
12/19 20:56, , 1F
12/19 20:56, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
理工
1
1