Re: [離散]鴿籠原理題目
※ 引述《lexwu200212 (胡椒)》之銘言：
: 小弟正在準備研究所考試
: 其中離散數學最近看到關於鴿籠的一題
: 題目如下
: 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不能帶入鴿籠"的話不是很奇怪嘛...
: 懇請教導!謝謝!
鴿籠原理直白地講就是：鴿子太多了，多過籠子的數量，所以沒辦法每隻都住單人房。
從鴿籠原理的敘述來看，
有兩個路線去操作：
A.希望鴿子越多越好，多到鴿子塞爆。
B.希望籠子越少越好，少到鴿子擠爆。
現在這個題目就是：
考慮適當類型的鴿子分配到哪些籠子就好了，其他就不管了。
這招可以行的通的原因就是在做這個動作的同時，
雖然鴿子變少了，跟 A 路線事與願違，
但是同時，我們也得以把不少籠子也扔了，使用 B路線前進。
現在問題就是：這兩方的拉距結果是不是 籠子的減少 強勢過 鴿子的減少？
有沒有辦法達到我們的希望目標：（要考慮的）鴿子比（可能的）籠子多。
從解答看起來，是行得通。
進一步講的話，再選定好 6個數字後，不計空集合，我們有 63 個子集可能，
把每一個子集可能都當成一隻鴿子，籠子則是加總出來的可能和值。
最多就六個數，所以可能和最高到 9+10+11+12+13+14=69，有 69 個籠子。
這些鴿子，我們可以把他們分成六級：
1個元素子集 2個元素子集 3個元素子集 4個元素子集 5個元素子集 6個元素子集
E D C B A S
最開始的想法，很自然就是 E級 D級 C級 B級 A級 S級，開始配到 69 個籠子，
但是如解答說的失敗了。
5個數和，最高就是 10+11+12+13+14 = 60，
所以 61,62,63,64,65,66,67,68,69 ，
這些籠子都很高級的，只有S級的鴿子"才有可能"可以住進去。
（有可能而以，還不一定夠格，如果6數是1,2,3,4,5,6這種草包組合還沒辦法配到。）
因此 61,62,63,64,65,66,67,68,69
每一個都要 S級：6個元素子集才有辦法配到，但一開始的六數一旦決定下來後，
就只會有一隻 S級的鴿子。
所以 61,62,63,64,65,66,67,68,69 這麼一大票籠子，其實最多就只有一個會配到鴿子。
那不如就不要管那個 6個元素子集 配到哪了，這樣少了一隻鴿子，但也踢掉 9個籠子，
一來一往的拉距後，就也達到我們想要的目標了。
這種局部的考量爆掉後，當然，其他的放哪都不重要了，
其他的再怎麼放，都改變不了，局部考量時發現的那個有超過一隻鴿子住的籠子的狀況，
其他不論放哪，先前考慮好後同一間的房客只會多，不會變少。
就好像打梭哈，前四張牌就有三條了之後，第五張不管是啥，都不會讓結局變只有一對。
當然，我們繼續再多考慮一些，還有一些其他的配法可以看。
用組合數算一下，立刻就可以得到：
E級:6隻鴿子 D級:15隻鴿子 C級:20隻鴿子 B級:15隻鴿子 A級:6隻鴿子
B級,C級,D級,E級 這些最多只能配發到 11+12+13+14=50號以下的籠子。
但現在有 6+15+20+15=56 隻鴿子要配 => 爆掉了。
所以其實考慮4個數以下的子集也是work的。
再往下呢？
C級,D級,E級 這些最多只能配發到 12+13+14=39號以下的籠子。
共有 6+15+20=41 隻鴿子要配 => 也爆掉了，還是 work。
D級,E級 這些最多只能配發到 13+14=27 號以下的籠子。
現在有 6+15=21 隻鴿子要配，C級這個最大宗的中產階級被砍掉了，
少了一堆鴿子可以用，但籠子卻沒少更多，結果就是不work了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 182.235.182.218
※ 編輯: Eeon 來自: 182.235.182.218 (10/04 04:44)
推
10/04 11:14, , 1F
10/04 11:14, 1F
討論串 (同標題文章)