Re: [理工] [離散] 鴿籠

[privatewind (傷神客)]

※ 引述《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)
推 hunter0904:是14+13+12+11+10? 你多打一個9