最後更新

[大學][離散]鴿籠原理的問題

[複製連結] 檢視: 1779|回覆: 3

pw859291

無名的居民

電梯直達

1^#

發表於 07-3-17 23:39:41 |只看該作者 |降序瀏覽大字中字小字正體化简体化

1.在一個房間裡面有十個人，每個人的年齡最少1歲，最多60歲(都是正整數)，
  請證明一定存在兩個團體(沒有相同的人)，這兩個團體的年齡總和相同。

2.收集{1,2, ... , n}的子集合的集合，這些集合裡面"任"兩個子集合至少有一個
  元素一樣，請證明最多會有2^{n-1}個子集合落在這個集合裡面。

因為第一次學...
不知道可否請懂的人能利用簡單的方式來證明呢
of course 要用鴿籠原理去證
感激不盡...這兩題卡了好久.....

轉播0 分享0 收藏0

回覆使用道具檢舉

傲月光希

名望的騎士

2^#

發表於 07-3-18 00:34:05 |只看該作者大字中字小字正體化简体化載入全部圖片

第一題

假設10個人的年齡分別是1,11,21,31,41,2,20,40,50,60呢?
那要怎麼年齡一樣?

既然分成兩個團體且年齡一樣，那兩個團體總合起來的數目不就是全部人年齡的總合?那就必須把全部的人的年齡總合一分為二
上面我舉的例子總合是奇數

除非，這10個人不只是分兩個團體而已，而是最多分10個團體(至少一人自成一個)
請解惑一下

進入數學版滿月祭III相簿1 2

回覆使用道具檢舉

pw859291

無名的居民

3^#

發表於 07-3-18 00:42:12 |只看該作者大字中字小字正體化简体化載入全部圖片

回答樓上的問題

這兩個團體的人數加起來不一定要剛好10個人喔
而且團體裡面只有一個人也是可以的
所以在解這個問題的時候，我們應該要先扣除掉空集合和全集合的情況(因為這兩種情況不可以)

您假設10個人的年齡分別是1,11,21,31,41,2,20,40,50,60
如果我挑兩個團體如下：{1, 21} = {2,20} 這兩個團體的年齡總合就會一樣
不知道這樣是否了解了呢？

回覆使用道具檢舉

傲月光希

名望的騎士

4^#

發表於 07-3-20 20:11:57 |只看該作者大字中字小字正體化简体化載入全部圖片

我問過我同學，他是這樣解第一題的

考慮一個團體不超過4個人，則可能的組合法有C(10,1)+C(10,2)+C(10,3)+C(10,4)=10+45+40+210=305
如果這些組合中有年齡總合相同的，則將其中兩組給拆出來即為所求

因此假設全部都不同
我們可以知道，四個人一起的團體總合是介於4到240之間，所以根據鴿籠原理，存在兩組團體的年齡總合是相同的
如果這兩組有相同的人，則將相同的人給去掉就是答案

回覆使用道具檢舉

最後更新返回清單

帳號		自動登入	取回密碼
密碼			註冊