抽屉原理

抽屉原理

抽屉原理：把多余n个的物品放入n个抽屉里，则至少有一个抽屉里的物品不少于两件。抽屉原理也叫鸽巢原理，它是组合数学的一个基本原理，最早由德国数学家狭利克雷提出，所以也成为狭利克雷原理。举例来说，桌上有十个猕猴桃，要把这十个猕猴桃放到九个抽屉里，无论怎样放，有的抽屉能够放一个,有的能够放两个，有的能够放五个。但最终我们会发现，当把九个都放入至少一个时，总会找到剩下的一个会放入一个已经放进猕猴桃的抽屉，至少我们能够找到有那么一个抽屉里面至少放了两个猕猴桃。

什么是抽屉原理

01 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的"抽屉原理"。 02 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。抽屉原理又称鸽巢原理，它是组合数学的一个基本原理，最先是由德国数学家狭利克雷明确地提出来的，因此，也称为狭利克雷原理。 把3个苹果放进2个抽屉里，必须有一个抽屉里放了2个或2个以上的苹果。这个人所皆知的常识就是抽屉原理在日常生活中的体现。用它能够解决一些相当复杂甚至无从下手的问题。 03 抽屉原理的一般含义为:"如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。" 04 构造抽屉的方法 运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。例如，属相是有12个，那么任意37个人中，至少有几个人属相相同呢?这时将属相看成12个抽屉，则一个抽屉中有 37/12，即3余1，余数不考虑，而向上考虑取整数，所以这里是3+1=4个人，但这里需要注意的是，前面的余数1和这里加上的1是不一样的。因此，在问题中，较多的一方就是物件，较少的一方就是抽屉，比如上述问题中的属相12个，就是对应抽屉，37个人就是对应物件，因为37相对12多。

抽屉原理

原集合的非空子集个数：
S=C(10,1)+C(10,2)+...+C(10,10)=2^10-1=1023 [式中C(10,1)表示从10个元素中任取1个元素的组合数，依次类推]

又∵任取一个子集，其各数之和为T,必定有
10+11+12+13+14≤T≤99+98+...+90
即63≤T≤945
∴可以构造子集中各数之和的抽屉，抽屉个数为(935-63+1=)873
将1023个子集放入以上873个抽屉
根据抽屉原理，必有至少2个子集放入同一抽屉

故一定存在2个不同的子集,其元素之和相等;
划去它们共有的数字,
可得两个无公共元素的非空子集,其所含各数之和相等