MQ75 --- Set

用戶27207

2013-02-11 6:25 am

MQ75 --- SetDifficulty: 55%Set I contains 10 elements randomly chosen from {1,2, … , 100}, prove that it must exist 2 disjoint subsets of I such that their sum of elements are equal.

回答 (1)

用戶2053

2013-02-13 1:57 am

✔ 最佳答案

10 個元素之和最多 91 + 92 + 93 + 94 + 95 + 96 + 97 + 98 + 99 + 100 = 955。
故該10 個元素之子集元素和範圍由 1 至 955。
每一元素取或不取共 2¹º 個組合 ,
扣除空集後該 10 個元素之子集數目共 2¹º - 1 = 1023 > 955 個。
由抽屜原理, 必定存在兩個元素不全相同而元素和一樣的子集,
注意該兩個子集任何一個不為另一個之子集(否則元素和將不能相同!)
最後把該兩個子集共有之元素(如有的話)全部扣除, 得到的兩個新子集即為所求。

👍 0 👎 0