[離散]鴿籠原理題目
小弟正在準備研究所考試
其中離散數學最近看到關於鴿籠的一題
題目如下
Let S be a set of 6 positive integers whose maximum is at most
14. Show that the sums of the elements in all the non-empty subsets of S
cannot all be distinct
這題很經典
解法也找得到.如下
There are 2^6-1=63 non-empty subsets and the sum of every subset of
S is at most 9+10+...+14=69. So the pigeonhole pricincple cannot be
applied directly. Instead, let's consider subsets of size at most 5.
Their total sum is at most 10+11+..+14=60. There are 62 non-empty subsets
with at most 5 elements. So at least two of them have equal sum.
在這解答中所寫
由於6個elements的subset無法直接使用鴿籠
所以計算的subset僅有5個elements
但這裡小弟對他這個解答的觀念有點問題
這個解答的方式感覺像是
因為6個不能用
所以用5個才能找出答案
可是這樣子的解答不就不完整了嗎?
另外找的的一份解答大同小異
只是他的說法改變成"不考慮空集合和集合本身這兩個subset"
空集合不計我可以理解為沒有元素所以沒有和
但是為什麼不計本身?
理由是因為"六個elements不能帶入鴿籠"的話不是很奇怪嘛...
懇請教導!謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.22.247
→
10/04 00:48, , 1F
10/04 00:48, 1F
推
10/04 01:28, , 2F
10/04 01:28, 2F
→
10/04 01:29, , 3F
10/04 01:29, 3F
→
10/04 01:30, , 4F
10/04 01:30, 4F
推
10/05 12:20, , 5F
10/05 12:20, 5F
→
10/05 12:21, , 6F
10/05 12:21, 6F
→
10/05 12:22, , 7F
10/05 12:22, 7F
→
10/05 12:24, , 8F
10/05 12:24, 8F
→
10/05 12:25, , 9F
10/05 12:25, 9F
討論串 (同標題文章)