高中数学培优竞赛强基计划讲义数学竞赛教案：第05讲 子集

第5讲 子集 本讲内容有子集、子集的个数、集合的划分及子集的应用。 设表示任意元素，表示两个集合。若 ，则 ，即集合是集合的子集。规定空集是任何集合的子集。 子集是由原集合中的部分元素构成。对于由个元素组成的集合，它的每一个子集中元素的构成，都是对这个元素进行选择的结果。由于对每一个元素的选择都有两种可能（选上或不选），因此，对这个元素共有种不同选择结果，即由个元素组成的集合共有个不同子集。其中，不同的非空子集有个，不同的真子集有个。 A类例题 例1 求集合的子集的个数。 分析 欲求集合的子集的个数，可先求出集合的元素的个数。 解 由，得。 当时， 原方程的解集为空集； 当时， 原方程的解集为单元素集； 当时， 原方程有两个不等的实数解。 所以，当时，集合，有1个子集； 当时，集合，有2个子集； 当时，集合，有4个子集‘ 例2 求满足的集合的个数。 分析 本题要求的是集合中，必定含有元素的子集的个数，只要求出集合的子集数。 解 由集合的子集数为，得所求集合的个数为8。 例3 已知集合，对，定义为中所有元素之和。求全体的总和。 分析 要求出全体的总和，只要求出每个元素出现的次数。 解 由集合元素的互异性，得集合中某个元素在总合中出现的次数，就是集合中含有该元素的子集数。所以， 全体的总和。 [来源:学科网ZXXK] 情景再现 1．设集合，。 求集合的子集的个数。 2．若数集，则的值是_____。（1998年第九届“希望杯”高一） 3．设非空集合，且当时，必有，问：这样的共有多少个？ B类例题 例4 在某次竞选中，各个政党共作出种不同的诺言，任何两个政党都至少有一种公共诺言，但没有两党作出完全相同的诺言。试证明，政党的数目不多于个。 （1972年加拿大数学竞赛） 分析 这是一道有实际背景的问题。首先应选择适当的数学模型刻画这一问题。由题意，将“诺言”作为元素，运用集合进行分析和研究。 证明 将种不同的诺言构成集合，则每一个政党所作的诺言构成的集合是集合的子集。因而政党数应不大于集合的子集数。 又任何两个政党都至少有一种公共诺言，所以任何两个政党所对应的子集不可能是一对互补的子集。故政党数。 例5 证明：任意一个有限集的全部子集可以这样排列顺序，使得任何两个相邻的子集仅相差一个元素。 （1972年波兰数学奥林匹克） 分析 本题可采用构造方法进行证明，即对任意一个有限集的全部子集给出一个排列方法，满足题设的要求。为此，可从特殊情况入手进行探索。 [来源:学科网] 若有限集元素的个数 时，子集数为2，可排列为； 当时，子集数为22，可排列为； 当时，子集数为23，可排列为 每增加1个元素，子集数增加1倍。将原来已排列好的所有子集分别增加一个新元素，得到又一列排列好的子集。再将排列好的子集倒序后，接排在原来已排好的子集列后面，得到符合条件的新的子集列。 证明 设有限集的元素个数为。 当时，子集数为2，全部子集可排列为:； 当时，子集数为22，全部子集可排列为:； 当时，子集数为23，全部子集可排列为: 若时，子集数为2k，全部子集可排列为:,且任何两个相邻的子集仅相差一个元素。 当 即增加一个元素 时，按下面的方法可得由个元素组成的有限集的全部子集的一个排列， 。 因为共2k个子集中任何两个相邻的子集仅相差一个元素，所以，共2k个子集中任何两个相邻的子集也仅相差一个元素。又与也相差一个元素，因此，上述由个元素组成的有限集的全部子集的一个排列是符合条件的排列。 由此，我们得到对任意一个有限集的全部子集的符合条件的排列方法，即原命题得证。 例6设，且当时，。求的最大值。 （1995年全国高中数学联赛） 分析 由题意，与不能同属于集合。按照集合的这一本质特征，构造具有最多元素的集合。 解 由，又与不能同属于集合，得。 由， 得集合已不可能与集合同为集合的子集。故。 设 ，经检验，是满足条件的集合，且。所以，的最大值为1870。 [来源:Z#xx#k.Com] 情景再现 4．在一次IMO竞赛中，k个领队共使用n种不同语言。如果任何两个领队至少使用一种共同语言，但没有任何两个领队使用的语言完全相同。求证： 。 5．已知，当时，与视为不同的对，则这样的对的个数有____________个。 （1993年全国高中数学联赛） 6．设集合是整数集的子集，其中的元素有正整数，也有负整数，且若（允许），则，求证：若，则 。 C类例题 例7 对及其每一个非空子集，定义一个唯一确定的“交替和”：对每一个子集按照递减的次序重新排列，然后从最大的数开始交替的减或加后继的数（例如，的“交替和”是的“交替和”是5）。对，求所有这些“交替和”的总和。 （第1届美国数学邀请赛） 分析 求所有这些“交替和”的总和的关键，在于每一个数字在“交替和”中出现的次数及符号。 解 对集合的全部子集分为两类：含元素的子集共有个，不含元素的子集也有个。 将含元素的子集与不含元素的子集相对应，得这两个子集的“交替和”恒为。 所以，所有这些“交替和”的总和为。当时，“交替和”的总和为。 例8 已知集合中有10个元素，每个元素都是两位数。求证：一定可以从中取出两个无公共元素的子集，使两个子集的元素和相等。 (1972年14届IMO) 分析 本题要求的是从集合的子集中，找到两个元素和相等的子集。这两个子集即使有公共元素，只要同时除去公共元素就可以满足题意。 证明 由集合中每个元素都是两位数，故它们的总和不超过1000。而集合共有个子集。由抽屉原理，得集合的子集中至少有两个子集的和相等。若这两个子集有公共元素，只要同时从这两个子集中同时除去公共元素，得到两个无公共元素的子集，且使两个子集的元素和相等。即命题得证。 情景再现 7．设集合。现对的任意一个非空子集，令表示中最大数与最小数之和，那么，所有这样的的算术平均值为___________。 8．由前个正整数组成的集合，从中任取个元素组成的子集，求证：集合中必有两个数使得，或者。 [来源:学*科*网] 习题5 1． 若，试确定的值。 2．已知集合，，若是的子集，且，则子集有多少个？ 3．若，且时，必有，求证：这样的子集共有个。 4．已知集合，对 将中所有元素的和记为，将分为互不相交的两个子集且，若，求的所有值。 5．矩形城市的道路非常规则，恰好东西向、南北向的道路分别有条。一位妇女住在城市的西南角，工作在东北角。她每天步行去工作。如果每个交叉路口不得经过两次，证明她所能选取的路线数目不大于。 （第9届加拿大数学竞赛） 6．已知集合，求满足至少含有两个元素且任意两个元素的差的绝对值大于1的子集的个数。 （1996年上海爱朋思杯赛） 7． 设集合且对任意的，必有，则子集所含元素个数的最大值为___________________. (1991年河南省集训题) 8．已知集合是的子集，且具有下述性质：“中任意两个不同元素的和不能被117整除。”试确定的最大值并证明你的结论。（1997年全国高中数学联赛） 答案 情景再现 1． 解 由，得。 所以，集合的子集的个数为4。 2． 解 由题意，。经检验，的值是0或4。 3． 解 由题意，1与7，2与6，3与5中每一对数必须在同一个集合内。因此，所求集合的个数等同于以1与7，2与6，3与5及4为元素的集合的非空子集的个数。所以，这样的共有（个）。 4． 略证 设n种不同语言构成集合，则任何一个领队对应于集合中不互补的非空子集。所以， 。 5． 解由集合都是的子集，且。当时，有1种取法；当为一元集时，有2种取法；当为二元集时，有4种取法；当为三元集时，有7种取法。故不同的对有（个）。 6． 证明 设集合中，最小的正整数为，最大的负整数为。 由 则。又，则不可能是非零整数（否则，与分别是集合中最小的正整数和最大的负整数矛盾），即。 由题意，易得。 综上，。 若，则 。即原命题得证。 7． 略解 集合中元素，以最大数出现的次数等于集合的非空子集数，以最小数出现的次数等于集合的非空子集数。所以，所求的平均值为 。 8． 略证 设子集，且。 作差，得 ，且。 于是 , 由抽屉原理，必有 ； 或 。即原命题得证。 习题5 1． 略解 。 经检验，的值为或2。 2． 解1 由集合的子集中除去不含集合中元素的子集，得子集 共有（个）。 解2 子集的元素是由集合的任意一个子集中的元素，与集合的任意一个非空子集中的元素组成。所求的子集共有（个）。 3． 证明 由题意，1与，2与中每一对数必须在同一个集合内。因此，所求集合的个数等同于以1与，2与及为元素的集合的非空子集的个数。所以，这样的共有（个）。 4． 略解 由题意，。 因而，是3的倍数。 若，集合取集合中形如的元素构成，集合取集合中形如的元素构成，则集合满足题设要求； 若，集合取集合中形如的元素构成，集合取集合中形如的元素构成，则集合满足题设要求。 所以，所求的值为。 5． 略证 设条道路构成集合。这位妇女的每条路线对应于集合的一个子集。所以，他所能选取的路线数不大于集合的子集数，即有。 6． 略解 设表示集合满足题设条件的子集数。考察集合满足题设条件的子集构成。它的满足条件的子集可分为两类：一类不含元素，即集合中满足条件的子集，应有个；另一类含元素，此类子集或者是集合中满足条件的子集有个，或者是等有k个。因此， 易知， ， ， 由上式可依次推得， 7． 略解 由 构造满足条件且元素最多的子集： [来源:学|科|网] 共有元素67个。 8． 略解 将1997按除以117的不同余数分为117类：[0]，[1]， [116]（[n]表示除以117的余数为n）. 由，得每类各18个元素，其余各类各17个元素。 由题意，余数之和为117的两类不能同在一个子集内，从而构造含元素最多的子集：取类的所有元素及[0]类的一个元素构成集合，此时共有元素个。即的最大值为995。 （证明略） 学科网 w。w-w*k&s%5￥u 学科网 w。w-w*k&s%5￥u