集合的分划与子集族(打印)

集合的划分与子集族 即奥林匹克小丛书集合的划分与子集族 即奥林匹克小丛书 集合集合 一册的第一册的第 4 5 讲 讲 一 集合的划分一 集合的划分 例例 1 将集合 将集合分为分为个互不相交的子集个互不相交的子集使得 使得 1 2 1989 117 1 2 117 i A i 1 每个 每个都含有都含有个元素 个元素 2 每个 每个中各元素之和都相同 中各元素之和都相同 i A17 i A 例例 2 对一个由非负整数组成的集合 对一个由非负整数组成的集合 定义 定义是满足下述条件的有序对是满足下述条件的有序对的对数 的对数 S s r n 12 s s 且且 问能否将非负整数集分划为两个集合 问能否将非负整数集分划为两个集合和和 使得对任意使得对任意均有均有 12 s sS 1212 ss ssn ABn AB rnrn 例例 3 3 设集合 设集合 求最小的正整数 求最小的正整数 使得对 使得对的任意一个的任意一个分划分划 1 2 Am mA14 1214 A AA 一定存在某个集合一定存在某个集合 在 在中由两个元素中由两个元素 满足 满足 114 i Ai i A a b 4 3 bab 例例 4 证明 可以把自然数集分划为 证明 可以把自然数集分划为个非空子集 使得对任何个非空子集 使得对任何个满足关系式个满足关系式的自然的自然100399abc 数数 都可以从中找出两个数属于同一子集 都可以从中找出两个数属于同一子集 a b c 例例 5 设集合 设集合和和是集合是集合的两个的两个分划 已知对任意两个交集为空集的分划 已知对任意两个交集为空集的 12 n A AA 12 n B BB Mn 集合集合 均有 均有 求证 求证 1 ij A Bi jn ij ABn 2 2 n M 例例 6 设自然数分划成 设自然数分划成个互不相交的子集 个互不相交的子集 求证其中必有某个子集 求证其中必有某个子集 它 它r 12r NAAA A 具有如下性质具有如下性质 存在 存在使对任何正整数使对任何正整数 都能找到 都能找到 满足 满足P mN k 12 k a aaA 1 1 11 jj aamjk 例例 7 将正整数集拆分成两个不相交的子集 将正整数集拆分成两个不相交的子集 满足条件 满足条件 1 2 中没有两个不同中没有两个不同 A B1A A 的元素 使它们的和形如的元素 使它们的和形如 3 中也没有两个不同的元素 其和具有上述形中也没有两个不同的元素 其和具有上述形 220 1 2 k k B 式 式 证明 这种拆分可以以惟一的方式实现 并确定证明 这种拆分可以以惟一的方式实现 并确定所属的子集所属的子集2007 2008 2009 例例 8 平面上横纵坐标均为有理数的点叫有理点 求证 平面上的全部有理点可以分成 平面上横纵坐标均为有理数的点叫有理点 求证 平面上的全部有理点可以分成个两两互不个两两互不3 相交的集合 满足条件 相交的集合 满足条件 1 在以每个有理点为圆心的任一圆内一定包含 在以每个有理点为圆心的任一圆内一定包含个点分属这个点分属这个集合 个集合 33 2 下任何一条直线上都不可能有 下任何一条直线上都不可能有个点分属这个点分属这个集合个集合33 例例 9 设 设 对对的任一非空子集的任一非空子集 当 当中任意两数之中任意两数之 1 2 2008 1004 2009 3014AM ABB 和不属于和不属于时 称时 称为为自由集 如果自由集 如果且且均为均为自由集 那自由集 那MBM 1212 AAA AA 12 A AM 么称有序对为么称有序对为为为的一个的一个划分 试求划分 试求的所有的所有划分的个数划分的个数 12 A AAM AM 二 二 族族C 例例 10 试证 任一有限集的全部子集可以排定次序 使得任何相邻的两个子集都相差一个元素 试证 任一有限集的全部子集可以排定次序 使得任何相邻的两个子集都相差一个元素 例例 11 在某次竞选中各政党作出 在某次竞选中各政党作出种不同的诺言 有些政党可以作某些相同的诺言 现知其种不同的诺言 有些政党可以作某些相同的诺言 现知其 0n n 中每两个政党都至少作了一个相同的诺言 但没有两个政党的诺言完全相同 求证 政党个数中每两个政党都至少作了一个相同的诺言 但没有两个政党的诺言完全相同 求证 政党个数 1 2n 例例 12 设正整数 设正整数 各不同的正整数各不同的正整数有下列性质 对集合有下列性质 对集合的任的任5n n 12 n a aa 12 n Sa aa 何两个不同的非空子集何两个不同的非空子集和和 中所有数的和与中所有数的和与中所有数的和都不会相等 在上述条件下 中所有数的和都不会相等 在上述条件下 ABAB 求求的最大值的最大值 12 111 n aaa 三 求解子集族三 求解子集族 例例 13 已知集合 已知集合 求集合 求集合的具有下列性质的子集个数 每个子集至少含有的具有下列性质的子集个数 每个子集至少含有各元各元 1 2 10A A2 素 且每个子集中的任何两个元素的差的绝对值大于素 且每个子集中的任何两个元素的差的绝对值大于1 例例 14 对于正整数 对于正整数 如果存在集合 如果存在集合的子集族的子集族满足 满足 1 2n 1 2 n 12 n A AA 1 i iAin 2 若 若 则 则 3 任意 任意 1 2 ij i jn ji iAjA 1 2 i jn ij AA 则称则称是是 和谐数和谐数 证明 证明 1 是和谐数 是和谐数 2 除 除外 其余的外 其余的都是和谐数都是和谐数n72 3 4 5 6n 例例 15 集合 集合 试作出 试作出的三元子集族的三元子集族 满足 满足 1 的任一二元子集的任一二元子集 1 2 6 XkkN XAX 至少被族至少被族中的一个三元子集包含 中的一个三元子集包含 2 A 2 6k A 四 有关子集族的最值问题四 有关子集族的最值问题 例例 16 集合 集合 是是的一族非空子集 当的一族非空子集 当时 时 至多有两至多有两 0 1 2 9A 12 k B BB Aij ij BB 个元素 求个元素 求的最大值的最大值k 例例 17 设 设满足 对任何整数满足 对任何整数及及中的任意数中的任意数 可以相同 可以相同 0 1 2 29A kA a b a b 均不是两个相邻整数之积 试确定所含元素个数最多的均不是两个相邻整数之积 试确定所含元素个数最多的30abk A 例例 18 设 设 对 对的任意一个的任意一个元子集元子集 若存在 若存在 使得 使得且且 1 2 1997A A999X x yX xy x y 则称则称为好集 求最大自然数为好集 求最大自然数 使得任一含有 使得任一含有的的元子集都为好集元子集都为好集X a aA a999 集合的分划与子集族集合的分划与子集族 1 已知集合 已知集合 可以分为 可以分为个互不相交的三元组个互不相交的三元组 其中 其中 1 2 31 3Ann n x y z3xyz 则满足上述要求的两个最小的正整数则满足上述要求的两个最小的正整数 n 2 设 设是一个有是一个有个元素的集合 选取个元素的集合 选取的两个子集 可以相同 的两个子集 可以相同 使得它们的并集是 使得它们的并集是 选取的顺 选取的顺S6SS 序无关紧要 如序无关紧要 如与与表示同一种取法 这样的取法有表示同一种取法 这样的取法有 a cb c d e f b c d e fa c 种种 3 设集合 设集合 求证 在 求证 在或或中含有三个元素中含有三个元素 使得 使得 1 2 9 ABAB AB x y z 2xyz 4 已知集合 已知集合是是的子集 且的子集 且中任一两个元素之和均不能被中任一两个元素之和均不能被整除 求集合整除 求集合M 1 2 2008A M3 中元素个数的最大值中元素个数的最大值M 5 试证 对于每个整数 试证 对于每个整数 都能找到一个最小的整数 都能找到一个最小的整数 使在集合 使在集合分成分成1r 1h r 1 2 h r 组的任何分划中 都存在整数组的任何分划中 都存在整数 使数 使数含于分划的同一组中含于分划的同一组中r0 1axy ax ay axy 6 已知这个空间被分成互不相交的 已知这个空间被分成互不相交的个非空集合 求证 必有一个平面 它至少与其中的四个集合个非空集合 求证 必有一个平面 它至少与其中的四个集合5 有公共点有公共点 7 是是的分划 即的分划 即 并且 并且两两的交集都是空集 两两的交集都是空集 1 2 Xn A B CXABCX A B C 如果如果中各取一个元素 那么每两个的和都不等于第三个 求中各取一个元素 那么每两个的和都不等于第三个 求 A B C maxmin AB C 8 1 证明 正整数集 证明 正整数集可以表示为三个彼此互不相交的集合的并集 使得 若可以表示为三个彼此互不相交的集合的并集 使得 若 且 且 N m nN 或或 则 则属于不同的集合属于不同的集合2mn 5 m n 2 证明 正整数集 证明 正整数集可以表示为四个彼此互不相交的集合的并集 使得 若可以表示为四个彼此互不相交的集合的并集 使得 若 且 且 N m nN 或或 则 则属于不同的集合 并说明此时将属于不同的集合 并说明此时将表示为三个彼此互不相交的集合的并表示为三个彼此互不相交的集合的并2 3mn 5 m n N 集时 命题不成立集时 命题不成立 9 确定所有的正整数 确定所有的正整数使得集合使得集合可以分成可以分成个互不相交的子集 每个子集中元素之和相个互不相交的子集 每个子集中元素之和相n 1 2 n 5 等等 10 设 设为正整数 为正整数 是是与与之间 包括这两个数在内 的所有整数组成的集合 之间 包括这两个数在内 的所有整数组成的集合 k k M 2 2kk 2 23kk 能否将能否将拆分为两个不相交的子集拆分为两个不相交的子集 使得 使得 k M A B 22 x Ax B xx 11 给定正整数 给定正整数 求具有下列性质的正整数 求具有下列性质的正整数的最小值 把集合的最小值 把集合任意分成两个任意分成两个3n m 1 2 Sm 互不相交的非空子集的并集 其中必有一个子集内含有互不相交的非空子集的并集 其中必有一个子集内含有个数 不要求它们互不相同 个数 不要求它们互不相同 n 使得 使得 12 n x xx 121nn xxxx 12 正整数 正整数具有下列性质 把集合具有下列性质 把集合任意分成两个互不相交的子集 总有某个子任意分成两个互不相交的子集 总有某个子4n 1 2 n Sn 集 它含有三个数集 它含有三个数 允许 允许 使得 使得 求这样的 求这样的的最小值的最小值 a b cab abc n 13 设 设为为个正实数组成的集合 对个正实数组成的集合 对的每个非空子集的每个非空子集 令 令为为中所有元素之和 求证 中所有元素之和 求证 SnSA fAA 集合集合可以拆分成可以拆分成个互不相交的子集 每个子集中的最大数与最小数之差为个互不相交的子集 每个子集中的最大数与最小数之差为 fA AS A n2 14 试求所有正整数 试求所有正整数 使集合 使集合可以分解为两个互不相交的子集可以分解为两个互不相交的子集 k 1990 1991 1990Mk A B 且使两个集合中的元素之和相等且使两个集合中的元素之和相等 15 给定集合 给定集合 其中 其中为非零复数 可视为平面上非零向量 为非零复数 可视为平面上非零向量 121993 SZ ZZ 121993 Z ZZ 求证 可以把求证 可以把中元素分成若干子集 使得中元素分成若干子集 使得S 1 中每个元素属于且仅属于一个子集 中每个元素属于且仅属于一个子集 2 每一子集中任一复数与该子集所有复数之和的夹角 每一子集中任一复数与该子集所有复数之和的夹角S 不超过不超过 90 3 将任二子集中复数分别作和 所得和数之间夹角大于 将任二子集中复数分别作和 所得和数之间夹角大于 90 1 16 设 设都是正整数 并且都是正整数 并且 求证 集合 求证 集合 r s nrsn 12 rnnn A rrr 构成构成的分划的充要条件是的分划的充要条件是和和都与都与互质互质 12 snnn B sss 1 2 2Nn rsn 17 设集合设集合 求一个包含元素最多的集合 求一个包含元素最多的集合的子集的子集使得使得中任意三个元素中任意三个元素 1 2 21An ABBa 都有都有bcabc 18 集合 集合的所有子集中 有这样一族不同的子集 它们两两的交集都不是空集 那的所有子集中 有这样一族不同的子集 它们两两的交集都不是空集 那 0 1 2 9A 么这族子集最多有么这族子集最多有 个个 19 设集合 设集合 现对 现对的任一非空子集的任一非空子集 令 令表示表示中最大数与最小数之和 中最大数与最小数之和 1 2 2008A AX X X 则所有这样的则所有这样的的算术平均数为的算术平均数为 X 20 集合 集合的所有子集中全部元素之和的总和是的所有子集中全部元素之和的总和是 1 2 n 21 如果一个正整数集合中没有 如果一个正整数集合中没有个数是两两互质的 则称之为个数是两两互质的 则称之为 和谐和谐 的 问从的 问从 到到的整数集中的整数集中3116 和谐和谐 的子集的元素的最大数目是多少 的子集的元素的最大数目是多少 22 设 设是集合是集合的子集 且的子集 且中任意两个不同的数作和 所得的数两两不同 求中任意两个不同的数作和 所得的数两两不同 求 S 1 2 9 S max S 23 设 设 求最小正整数 求最小正整数使得使得中的每个中的每个元子集中都有元子集中都有个数能作为直角三角形个数能作为直角三角形 1 2 50A nAn3 的三边长的三边长 24 设 设为质数 考虑集合为质数 考虑集合满足以下两个条件的子集满足以下两个条件的子集 1 恰有恰有个元素 个元素 3p 1 2 2p AAp 2 中所有元素之和可被中所有元素之和可被整除整除Ap 25 设 设是一个固定的正整数 是一个固定的正整数 是一个无限集族 且每个集合中含有是一个无限集族 且每个集合中含有个元素 若个元素 若中的任中的任2r FrF 意两个集合的交集非空 求证 存在一个具有意两个集合的交集非空 求证 存在一个具有个元素的集合与个元素的集合与中的每一个集合的交集非空中的每一个集合的交集非空1r F 26 设 设 是一个是一个元集合 求最小的正整数元集合 求最小的正整数 使得存在 使得存在的子集的子集具有具有2 nnN SnkS 12 k A AA 如下性质 对如下性质 对的任意两个不同元的任意两个不同元 存在 存在 使得 使得为为的一元子集的一元子集S a b 1 2 jk j Aa b S 27 求最小的正整数 求最小的正整数 使 使的每个的每个元子集中都有两个数元子集中都有两个数使得使得 1 2 50A kAkab ab ab 28 是一个是一个元集合 元集合 中最多有多少个这样的三元子集 使得其中任意两个三元子集都恰好有一中最多有多少个这样的三元子集 使得其中任意两个三元子集都恰好有一SnS 个公共元个公共元 29 集合 集合 从 从中取出中取出个子集个子集满足下列条件 满足下列条件 1 1 2 15S Sn 12 n A AA 7 i A 2 3 对 对的任意三元子集的任意三元子集 都存在某个 都存在某个使得使得3 1 ij AAijn SM 1 k Akn 求这样一组子集的个数 求这样一组子集的个数的最小值的最小值 k MA n 30 设 设 对任意 对任意 可以相同 总有可以相同 总有 求 求的最大值的最大值 1 2 2002A a bA a babA A 31 称子集 称子集为好的 如果它具有下述性质 为好的 如果它具有下述性质 如果如果则则且且 1 2 11AM 2kA 21kA 空集和 空集和都是好的 都是好的 有多少个好子集