作者shinle14 ()
看板Grad-ProbAsk
标题[理工] 鸽笼
时间Sat Oct 19 10:04:46 2019
http://i.imgur.com/xXdZdi6.jpg
想问这题，一开始A的基数小於等於3就不懂了
-----
Sent from JPTT on my Samsung SM-A730F.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.76.5.42 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1571450688.A.A44.html
※ 编辑: shinle14 (42.76.5.42 台湾), 10/19/2019 10:05:30
1F：→ eric21489: 因为4以上鸽笼不成立 10/19 11:01
2F：→ eric21489: 证明3以下必定有相同元素和就等於不是所有非空子集都 10/19 11:05
3F：→ eric21489: 有唯一元素和 10/19 11:05
4F：→ eric21489: 3以下就只有{ 1 } ~ { 7, 8, 9 } 最多24个sum 10/19 11:07
5F：→ eric21489: 但有25种subset 10/19 11:07
6F：推 mi981027: 先了解题目在干嘛 每个非空子集合都会有一个元素和 10/19 11:10
7F：→ mi981027: 元素和的值域落在(1+2+3+4+5)~(9+8+7+6+5) 10/19 11:10
8F：→ mi981027: 把非空子集合的个数想像成鸽子，元素和值域想成笼子 10/19 11:10
9F：→ mi981027: 那只要证明值域的范围小於非空子集合个数(31) 10/19 11:10
10F：→ mi981027: 就可以用鸽笼证明一定有两个非空子集合元素和一样 10/19 11:10
11F：→ mi981027: 详解的证法楼上讲的很清楚了 就不赘述 10/19 11:10
12F：→ mi981027: 不过其实也不是4以上不成立啦 10/19 11:10
13F：→ mi981027: 也能直接用5个元素的情况来证 只是会麻烦一点 10/19 11:10
15F：→ skyHuan: 类似题，但笼>鸽直接鸽笼不一定会保证两个一样 10/19 12:51
16F：→ skyHuan: A<=6(蓝色)要找两个一样但没办法保证找到，我们缩小范围 10/19 12:51
17F：→ skyHuan: 去A<=5(红色)找，如果找得到代表蓝色也有两个一样 10/19 12:51
18F：→ skyHuan: 你这题就是A<=5找不到去A<=4找还是找不到就去A<=3 10/19 12:52
19F：→ shinle14: 谢谢各位，我研究一下 10/19 14:34
20F：→ mi981027: 熊熊发现上面打错... 10/20 00:07
21F：→ mi981027: 子集合的元素合值域是落在1~(9+8+7+6+5)才对... 10/20 00:07
22F：→ mi981027: 有误导的话非常抱歉qq 10/20 00:07
哈哈我有犹豫一下，还是谢谢mi大大～～
※ 编辑: shinle14 (42.76.106.117 台湾), 10/20/2019 10:44:27