第一讲 元素与集合(5)

集与偶子集个数相等，故均为个．

（2）设an(bn)表示Sn中全体奇（偶）子集容量之和． 若n(≥3)是奇数，则Sn的奇子集由如下两类：（1）Sn－1的奇子集；（2）Sn－1的偶子集与集{n}的并，于是得

an=an－1＋（bn－1＋n·2n－2），①

又Sn的偶子集可由Sn－1的偶子集和Sn－1的奇子集与{n}的并构成，所以 bn = bn－1＋（an－1＋n·2n－2），② 由①，②，便得an= bn．

若n（≥4）是偶数，同上可知 an=an－1＋（an－1＋n·2n－2）， bn = bn－1＋（bn－1＋n·2n－2），

由于n－1是奇数，由上面已证an－1= bn－1，从而an = bn． 综上即知，an = bn，n=3，4?

（3）由于Sn的每一个元素均在2n－1个Sn的子集中出现，所以，Sn的所有子集容量之和为2n－1（1＋2＋?＋n）=2n－2n（n＋1)． 又由（2）知，an=bn，所以

说明（2）的证明中，建立了递推关系．这也是解决“计数”问题的一个有效方法．

例4、设A是集合S={1，2，…1000000}的一个恰有101个元素的子集．证明：在S中存在数t1，t2，…t100，使得集合

际数学奥林匹克试题）

[分析及答案]

证明：考虑集合D={x－y|x，y∈A},则

若

，设

，则a=x＋ti，a=y＋tj，其中x，y∈A，则ti－tj=y－x∈D．

中，每两个的交集为空集．（2003年国

若ti－tj∈D，即存在x，y∈A，使得ti－tj=y－x，从而x＋ti= y＋tj，即所以，

的充要条件是ti－tj∈D．于是，我们只需在集合S中取出100个元素，使得

其中任意两个差都不属于D．

下面用递推方法来取出这100个元素．

先在S中任取一个元素t1，再从S中取一个t2，使得

这是因为取定t1

后，至多有10101个S中的元素不能作为t2，从而在S中存在这样的t2．若已有k(≤99)个S中的元素t1，t2，?，tk满足要求，再取tk＋1，使得t1，?，tk都不属于tk＋1＋D={ tk＋1＋x|x∈D}，这是因为t1，t2，?，tk取定后，至多有10101k≤999999个S中的数不能作为tk＋1，故在S中存在满足条件tk＋1．所以，在S中存在t1，t2，?，t100，其中任意两个的差都不属于D．

综上所术，命题得证．

说明：条件|S|=106可以改小一些．一般地，我们有如下更强的结论： 若A是S={1,2,?，n}的k元子集，m为正整数，满足条件n>(m－1)t1，?，tm，使Aj={x＋tj|x∈A}，j=1,?m中任意两个的交集为空集．

例5、求函数解答：由题设可得x2－3x＋2=y2－2xy＋x2， 即（2y－3）x=y2－2．

的值域．（2001年全国高中数学联赛试题）

，所以

则存在S中的元素

由上式知由

故x0≤1，于是

综上，所求的函数的值域为

说明：我们先求出了y的范围，这是不是函数的值域呢？第二部分说明了对于

中的任意一个数y0，总存在一个x0，使得，这就证明了

函数的值域是