鐵之狂傲

標題: [大學][離散]鴿籠原理的問題 [列印本頁]

作者: pw859291 時間: 07-3-17 23:39
標題: [大學][離散]鴿籠原理的問題
1.在一個房間裡面有十個人，每個人的年齡最少1歲，最多60歲(都是正整數)，
  請證明一定存在兩個團體(沒有相同的人)，這兩個團體的年齡總和相同。

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

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

作者: 傲月光希 時間: 07-3-18 00:34
第一題

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

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

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

作者: pw859291 時間: 07-3-18 00:42
回答樓上的問題

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

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

作者: 傲月光希 時間: 07-3-20 20:11
我問過我同學，他是這樣解第一題的

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

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

歡迎光臨鐵之狂傲 (https://gamez.com.tw/)