1002_高中数学竞赛系列讲座——抽屉原理(4)

一套很有用的数学竞赛丛书,老师学生皆宜

显然，必须找出一种能把前25个自然数分成6（7-1=6）个集合的方法，不过分类时有一个限制条件：同一集合中任两个数的比值在内，故同一集合中元素的数值差不得过大。这样，我们可以用如上一种特殊的分类法：递推分类法：

从1开始，显然1只能单独作为1个集合{1}；否则不满足限制条件。 能与2同属于一个集合的数只有3，于是{2，3}为一集合。

如此依次递推下去，使若干个连续的自然数属于同一集合，其中最大的数不超过最小的数的倍，就可以得到满足条件的六个集合。

（2）如果我们按照（1）中的递推方法依次造“抽屉”，则第7个抽屉为 {26，27，28，29，30，31，32，33，34，35，36，37，38，39}； 第8个抽屉为：{40，41，42， ，60}；

第9个抽屉为：{61，62，63， ，90，91}；

那么我们可以将例3改造为如下一系列题目：

（1）从前16个自然数中任取6个自然数；

（2）从前39个自然数中任取8个自然数；

（3）从前60个自然数中任取9个自然数；

（4）从前91个自然数中任取10个自然数；

都可以得到同一个结论：其中存在2个数，它们相互的比值在]内。 上述第（4）个命题，就是前苏联基辅第49届数学竞赛试题。如果我们改变区间[]（p＞q）端点的值，则又可以构造出一系列的新题目来。

例4．已给一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。（第14届1M0试题）

分析与解答：一个有着10个元素的集合，它共有多少个可能的子集呢？由于在组成一个子集的时候，每一个元素都有被取过来或者不被取过来两种可能，因此，10个元素的集合就有210=1024个不同的构造子集的方法，也就是，它一共有1024个不同的子集，包括空集和全集在内。空集与全集显然不是考虑的对象，所以剩下1024-2=1022个非空真子集。

再来看各个真子集中一切数字之和。用N来记这个和数，很明显： 10≤N≤91+92+93+94+95+96+97+98+99=855

这表明N至多只有855-9=846种不同的情况。由于非空真子集的个数是1022，1022＞846，所以一定存在两个子集A与B，

使得A中各数之和=B中各数之和。

若A∩B=φ，则命题得证，若A∩B=C≠φ，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出两个不相交的子集A1与B1，很显然

A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。

说明：本例能否推广为如下命题：

已给一个由m个互不相等的n位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。

请读者自己来研究这个问题。