苍溪中学课改2012数学竞赛教案：第04讲 子集

第 1 页 共 6 页 第 4 讲 子集 本讲内容有子集 子集的个数 集合的划分及子集的应用 设表示任意元素 表示两个集合 若 则 aBA BaAa BA 即集合是集合的子集 规定空集是任何集合的子集 AB 子集是由原集合中的部分元素构成 对于由个元素组成的集合 它的每一个子集中n 元素的构成 都是对这个元素进行选择的结果 由于对每一个元素的选择都有两种可能n 选上或不选 因此 对这个元素共有种不同选择结果 即由个元素组成的集合n n 2n 共有个不同子集 其中 不同的非空子集有个 不同的真子集有个 n 212 nn 2 A 类例题 例例 1 求集合的子集的个数 03 2 aaxxRxM 分析分析 欲求集合的子集的个数 可先求出集合的元素的个数 MM 解解 由 得 03 2 aaxx 6 2 124 2 xxaa 当时 原方程的解集为空集 62 aa或 0 当时 原方程的解集为单元素集 62 aa或 0 当时 原方程有两个不等的实数解 62 a 0 所以 当时 集合 有1个子集 62 aa或 M 当时 集合 有2个子集 62 aa或 0 xM 当时 集合 有 4 个子集 62 a 21 xxM 例例 2 求满足的集合的个数 edcbaPba P 分析分析 本题要求的是集合中 必定含有元素的子集的个数 只 edcbaba 要求出集合的子集数 edc 解解 由集合的子集数为 得所求集合的个数为8 edc823 P 例例 3 已知集合 对 定义为中所有元素 7 6 5 4 3 2 AAX XSX 之和 求全体的总和 XSS 分析分析 要求出全体的总和 只要求出每个元素出现的次数 XSS 解解 由由集合元素的互异性 得集合中某个元素在总合中出现的次数 就是集合AS 中含有该元素的子集数 所以 A 全体的总和 XS86402 765432 5 S 情景再现情景再现 1 设集合 14 2 xxyyxA 12 xyyxB 求集合的子集的个数 BA 2 若数集 则的值是 1998 年 希望 2 1 1 2 1 2 4 aaa a 杯 3 设非空集合 且当时 必有 问 7 6 5 4 3 2 1 AAa Aa 8 这样的共有多少个 A 第 2 页 共 6 页 B 类例题 例例 4 在某次竞选中 各个政党共作出种不同的诺言 任何两个政党p 0 p 都至少有一种公共诺言 但没有两党作出完全相同的诺言 试证明 政党的数目不多于 个 1972 年加拿大数学竞赛 1 2 p 分析分析 这是一道有实际背景的问题 首先应选择适当的数学模型刻画这一问题 由 题意 将 诺言 作为元素 运用集合进行分析和研究 证明证明 将种不同的诺言构成集合 则每一个政党所作的诺言构成的集合是集合pA 的子集 因而政党数应不大于集合的子集数 AA 又任何两个政党都至少有一种公共诺言 所以任何两个政党所对应的子集不可能是 一对互补的子集 故政党数 1 2 2 2 p p 例例 5 证明 任意一个有限集的全部子集可以这样排列顺序 使得任何两个相邻的子 集仅相差一个元素 1972 年波兰数学奥林匹克 分析分析 本题可采用构造方法进行证明 即对任意一个有限集的全部子集给出一个排 列方法 满足题设的要求 为此 可从特殊情况入手进行探索 若有限集元素的个数 时 子集数为2 可排列为 1 n 1 a 当时 子集数为22 可排列为 2 n 2211 aaaa 当时 子集数为23 可排列为3 n 112223123133 aa aaa aa a aa aa 每增加1个元素 子集数增加1倍 将原来已排列好的所有子集分别增加一个新元 素 得到又一列排列好的子集 再将排列好的子集倒序后 接排在原来已排好的子集列后 面 得到符合条件的新的子集列 证明证明 设有限集的元素个数为 n 当时 子集数为2 全部子集可排列为 1 n 1 a 当时 子集数为22 全部子集可排列为 2 n 2211 aaaa 当时 子集数为23 全部子集可排列为 3 n 若时 子集数为 112223123133 aa aaa aa a aa aa kn 2k 全部子集可排列为 且任何两个相邻的子集仅相差一个元素 kAAA 2 21 当 即增加一个元素 时 按下面的方法可得由个元素组成的1 kn 1 k a1 k 有限集的全部子集的一个排列 12 2 k A AA 1111 221 kk kkk aAaAaA 因为共2k个子集中任何两个相邻的子集仅相差一个元素 所以 12 2 k A AA 共2k个子集中任何两个相邻的子集也仅相差一个元 1111 221 kk kkk aAaAaA 素 又与也相差一个元素 因此 上述由个元素组成的有限集 kA2kAak 2 1 1 k 的全部子集的一个排列是符合条件的排列 由此 我们得到对任意一个有限集的全部子集的符合条件的排列方法 即原命题得 证 例例 6 设 且当时 MANnnnM 19951 Ax 求的最大值 1995 年全国高中数学联赛 Ax 15 A 分析分析 由题意 与不能同属于集合 按照集合的这一本质特征 构造xx15AA 具有最多元素的集合 A 第 3 页 共 6 页 解 解 由 又与不能同属于集合 得 1995 133 15 xx15A ANnnnA 1995134 1 由 得集合已不可能与集合同 133 8 15 1339 2 NnnnA 1 A 为集合的子集 故 A 设 经检验 是满足条件的集合 且 81 3 NnnnA 31 AA 所以 的最大值为1870 1870 31 AA A 情景再现情景再现 4 在一次IMO竞赛中 k个领队共使用n种不同语言 如果任何两个领队至少使 用一种共同语言 但没有任何两个领队使用的语言完全相同 求证 1 2 n k 5 已知 当时 与视为不同的对 321 aaaBA BA BA AB 则这样的对的个数有 个 1993 年全国高中数学联赛 BA 6 设集合是整数集的子集 其中的元素有正整数 也有负整数 且若AZ 允许 则 求证 若 则 a bA ab abA a bA abA C 类例题 例例 7 对及其每一个非空子集 定义一个唯一确定的 交替和 对 2 1 n 每一个子集按照递减的次序重新排列 然后从最大的数开始交替的减或加后继的数 例如 的 交替和 是的 交替和 是5 对 9 6 4 2 1 5 612469 求所有这些 交替和 的总和 第 1 届美国数学邀请赛 7 n 分析分析 求所有这些 交替和 的总和的关键 在于每一个数字在 交替和 中出现 的次数及符号 解解 对集合对集合的全部子集分为两类 含元素的子集共有个 不含 2 1 n n 1 2 n 元素的子集也有个 n 1 2 n 将含元素的子集与不含元素的子集相n 21k aaan n 21k aaa 对应 得这两个子集的 交替和 恒为 n 所以 所有这些 交替和 的总和为 当时 交替和 的总和为n n 1 27 n 44827 6 例例 8 已知集合中有 10 个元素 每个元素都是两位数 求证 一定可以从中取SS 出两个无公共元素的子集 使两个子集的元素和相等 1972 年 IMO 分析分析 本题要求的是从集合的子集中 找到两个元素和相等的子集 这两个子集S 即使有公共元素 只要同时除去公共元素就可以满足题意 证明证明 由集合中每个元素都是两位数 故它们的总和不超过1000 而集合共SS 有个子集 由抽屉原理 得集合的子集中至少有两个子集的和相等 若1024210 S 这两个子集有公共元素 只要同时从这两个子集中同时除去公共元素 得到两个无公共元 素的子集 且使两个子集的元素和相等 即命题得证 情景再现情景再现 7 设集合 现对的任意一个非空子集 101 NnnnM MX 令表示中最大数与最小数之和 那么 所有这样的的算术平均值为 X aX X a 第 4 页 共 6 页 8 由前个正整数组成的集合 从中任n2 21 NnnmNmM 取个元素组成的子集 求证 集合中必有两个数使得1 nMAA ji aa 或者 Aaa ji ij aa2 习题习题5 1 若 试确定的值 12 3 2 1 2 2 aaaa 2 已知集合 若是的 101 NnnnA 5 4 3 2 1 BCA 子集 且 则子集有多少个 CB C 3 若 且时 必有 121 NmmnNnA Aa 求证 这样的子集共有个 Aam 212 m 4 已知集合 对 将中所有元 1 NnkknnX XA A 素的和记为 将分为互不相交的两个子集且 若 ASXBA XBA 求的所有值 2 BSAS k 5 矩形城市的道路非常规则 恰好东西向 南北向的道路分别有条 一位妇nm 女住在城市的西南角 工作在东北角 她每天步行去工作 如果每个交叉路口不得经过两 次 证明她所能选取的路线数目不大于 第 9 届加拿大数学竞赛 nmf mn 2 6 已知集合 求满足至少含有两个元素且任意两个元 101 Nnnn 素的差的绝对值大于1的子集的个数 1996 年上海爱朋思杯赛 7 设集合且对任意的 必有 1001 NxxxA Ayx 则子集所含元素个数的最大值为 1991 年河南省集训题 yx 2A 8 已知集合是的 19971 21k aaaAnNnS S 子集 且具有下述性质 中任意两个不同元素的和不能被117整除 试确定的最Ak 大值并证明你的结论 1997 年全国高中数学联赛 答案答案 情景再现情景再现 1 解 026 12 14 2 2 xx xy xxy 由 得 028836 2 BA 所以 集合的子集的个数为4 BA 2 解 由题意 经检1042 aaaaaa或或 验 的值是0或4 a 3 解 由题意 1与7 2与6 3与5中每一对数必须在同一个集合内 A 因此 所求集合的个数等同于以1与7 2与6 3与5及4为元素的集合A 的非空子集的个数 所以 这样的共有 个 A15124 4 略证 设n种不同语言构成集合 则任何一个领队对应于集合中不互补PP 第 5 页 共 6 页 的非空子集 所以 1 2 2 2 n n k 5 解由集合都是的子集 且 当BA BA BA 321 aaaBA 时 有1种取法 当为一元集时 有2种取法 当为二元集 ABABA 时 有4种取法 当为三元集时 有7种取法 故不同的对有BAB BA 个 26743231 6 证明 设集合中 最小的正整数为 最大的负整数为 Axy 由 则 又 则不可能是 AyAx Ayx xyxy yx 非零整数 否则 与分别是集合中最小的正整数和最大的负整数矛盾 yx A 即 xyyx 0 由题意 易得 NnAnxAx 综上 ZnnxaaAAx 若 则 即原Aba Axnmbanxbmxa 命题得证 7 略解 集合中元素 以最大数出现的次数等于集合Mk 的非空子集数 以最小数出现的次数等于集合 11 knNn 1 2 k 的非空子集数 所以 所求的平均值为 101 nkNn k 10 2 22 10 22 2 22 1 12 1 09890 10 11 222 101 12 1 90 10 8 略证 设子集 且 121 n aaaA naaa n 2 121 作差 得 且 niaab ini 2 1 1 nabbb nn 2 121 于是 naaabbb nn 2 1 12121 由抽屉原理 必有 Aaaaaaajiab njijinji 11 或 即原命题得证 2 1jniii aaaab 习题习题 5 1 略解 1 324 aaa 或或 2 1 2113aaaaa 或或 经检验 的值为或2 a4 2 解1 由集合的子集中除去不含集合中元素的子集 得子集 共有ABC 个 99222 510 解2 子集的元素是由集合的任意一个子集中的元素 与集合C 10 9 8 7 6 的任意一个非空子集中的元素组成 所求的子集共有BC 个 992 12 2 55 第 6 页 共 6 页 3 证明 由题意 1与 2与中每一对数必须在同一个集合12 m 22 m 内 因此 所求集合的个数等同于以1与 2与及AA12 m 22 m 为元素的集合的非空子集的个数 所以 这样的共有 个 mA12 m 4 略解 由题意 1 6 1 3 1 kkXSBS 因而 是3的倍数 1 kk 或 若 集合取集合中形如的元素构成 集合取mk3 AX233 mm 或B 集合中形如的元素构成 则集合满足题设要求 X13 mBA 若 集合取集合中形如的元素构成 集合13 mkAX133 mm 或 取集合中形如的元素构成 则集合满足题设要求 BX23 mBA 所以 所求的值为 k 133Nmmm 或 5 略证 设条道路构成集合 这位妇女的每条路线对应于集合的一个子集 mnPP 所以 他所能选取的路线数不大于集合的子集数 即有 nmfP mn nmf2 6 略解 设表示集合满足题设条件的子集数 k a 1 NnknnAk 考察集合满足题设条件的子集构成 它的 21 2 NnknnAk 满足条件的子集可分为两类 一类不含元素 即集合中满足条件的子集 2 k 1 k A 应有个 另一类含元素 此类子集或者是集合中满足条件的子集有 1 k a2 k k A 个 或者是等有k个 因此 k a 2 2 2 2 1 kkkk 易知 由上 21 kkk aaak kN 3 1 1 3 a 4 3 1 3 1 4 2 4 a 式可