第二讲 有限集元素的数目讲义-2026年高中数学竞赛

第二讲 有限集元素的数目 解决一个有限集有多少个元素的问题有时比我们想象的要困难得多, 因为一个有限集可以是概括地给出, 由它的元素所同时满足的性质来确定它的元素的个数常常需要用到较复杂的技巧。本节只讨论一些简单的问题。 1. 有限集的阶 有限集 的元素数目叫做这个集合的阶,记作 (或 )。 例 1 设集合 ,集合 。求 。 解 形如 的数可分为 3 类(即 时三种类型): 其中只有形如 的数是形如 的数。令 1 得 。所以 。 在这里, 我们采用了列举出集合的全部元素的方法来求其元素的数目。当一个集合的元素较多或者集合元素的性质较复杂时, 这种方法是很难奏效的, 这时必须另辟蹊径。 例 2 设 是 的子集,且满足条件: 当 时, 。求 的最大值。 解 因 ,可知 。又 ,所以 与 这些数彼此不同,且每对 与 不能同时在 中出现。因此 另一方面,设 , 则 ,且 中没有一个数是另一个数的 15 倍。 事实上,设 ,若 ,则 ; 若 ,则 ,故 。 综上所述, 的最大值为 1870 。 例 3 设 是任意一个 11 元实数集合。令集合 。 求集合 的元素个数的最小值。 解 先证明 。考虑到将 中的所有元素均变为原来的相反数时,集合 不变，故不妨设 中正数个数不少于负数个数。下面分类讨论: 情况一: 中没有负数。 设 是 中的全部元素,这里 ,于是 上式从小到大共有 个数,它们均是 的元素,这表明 。 情况二: 中至少有一个负数。 设 是 中的全部非负元素, 是 中的全部负元素。 不妨设 其中 、 为正整数， ，而 ，故 。于是有 它们是 中的 个元素,且非正数; 又有 它们是 中的 7 个元素,且为正数。故 。 由此可知, 。 另一方面,令 ,则 是个 17 元集合。 综上所述， 中元素个数的最小值为 17。 例 4 设 是 的一个子集，且对 中的任意三个不同的元素 ,都有 。求 的最大值。 解 设 。则 。设 其中 ,且 。由题设知 其中 (否则集合 中就有三个元素 ,使得 ,且 为偶数,所以 , 。从而 是 中互不相同的元素。因此 ,即 。所以 又当 时,对 中的任意两个不同的元素 ,都有 ,从而 满足题意。 综上所述, 的最大值为 。 2 容斥原理 容斥原理 I 对 个有限集 ,有 其中, 表示有限集合 的元素个数。 该结论可用数学归纳法或“贡献法”来证明。 注意到对 个集合 ,有如下的交、并对偶律: 故当全集 为有限集时,有 这样，容斥原理 I 即与下面的容斥原理 II (或称为逐步淘汰原理)等价。 容斥原理 II 对有限集 的 个子集 ,有 上述两种形式的容斥原理在 的情形是基本且重要的。 例 5 在不大于 1000 的正整数中,有多少个数既不被 5 整除又不被 7 整除? 这些正整数的和是多少? 解 设不大于 1000 的正整数组成集合 ,对 ,设 中所有 的倍数组成集合 ，其中 。 由容斥原理得，所求正整数的个数为 这些正整数的和为 注 在求元素个数时,我们直截了当地应用容斥原理; 在求元素之和时,则采用了与容斥原理同样的思想。 例 6 将 的长方体分成 个 的小正方体。求长方体的一条对角线穿过的小正方体的个数。 解 设长方体占据的空间区域为 将质点沿对角线从 穿行到 的路径用参数 表示为 在 递增的过程中,当且仅当 中至少有一个为整数时,质点将穿入一个新的小正方体,这里 。设 则有 。 又记 ,则 从而 同理得 。 故由容斥原理得，质点一共穿过的小正方体个数为 3 子集类的计数 有时,我们可以将某些集合取来作为元素构成一个新的集合,如 , 就是一个含有 4 个元素 的集合。特别地,将有限集的若干子集作为元素构成的集合叫做原集合的一个子集类。子集类中所含原来集合的子集数目叫做该子集类的阶。 最常见也是最基本的子集类是由有限集 的全体子集所构成的所谓 类 。 设 。由于作 的子集时,每个元素都有取与不取两种可能,故 。 例 7 对于 和它的每个非空子集,我们定义 “交替和”如下: 把子集中的数按从大到小的顺序排列,然后从最大的数开始交替地减、加各数 (例如, , 的交替和是 ,而 的交替和就是 5 )。对于 ,求所有这些交替和的总和。 解 集合 的非空子集共有 个。由于集合 , 的子集中含有 的子集的个数恰好为集合 的子集的个数,所以 中每个元素在子集中均出现 次。 由排列组合知识,可计算1,2,3,4,5,6在子集中按从大到小的顺序排列时各有 32 次在奇数位, 32 次在偶数位, 因此子集中这些数的交替和的总和为 0 ; 而 7 也出现 64 次,且均取正值,所以所有子集的交替和的总和为 。 例 8 已知集合 为 的一族非空子集,并且 时, 至多有两个元素。求 的最大值。 解 首先至多含 3 个元素的 的非空子集有 这些集合的交至多有两个元素, 否则两集合相等, 矛盾。 因此 。下面证明 。 设 为满足题设的子集族。若 ，且 ，设 ，则 与 不能同时含于 中，因两集合至少有 3 个公共元素。以 代 ，则 中元素数目不变。仿此对 中所有元素数目多于 4 的集合 作相应替代，替代后子集族 中的每个集合都是元素数目不多于 3 的非空集合，故 。 所以， 的最大值为 175 。 例 9 给定整数 ，记 为集合 的满足如下两个条件的子集 的元素个数的最小值: (a) ; (b) 中的元素(除 1 外)均为 中的另两个(可以相同)元素的和。 (1) 求 (3)的值； (2) 求证: 。 解(1)设集合 ，且 满足(a)、(b)。则 。 由于 不满足 (b),故 。 又 , 都不满足 (b),故 。 而集合 满足 (a)、(b),所以 。 (3) 首先证明 ① 事实上,若 ,满足 (a)、(b),且 的元素个数为 。 令 ,由于 ,故 。 又 ,所以,集合 ,且 满足 (a)、(b)。从而 其次证明: ② 事实上,设 满足 (a)、(b),且 的元素个数为 。令 由于 所以 ,且 。而 从而 满足 (a)、(b),于是 由①、②得 ③ 反复利用②、③可得 学科网（北京）股份有限公司 $