数学奥赛辅导第九讲

1 数学奥赛辅导第九讲 组合恒等式 组合不等式 知识 方法 技能 组合恒等式组合恒等式 竞赛数学中的组合恒等式是以高中排列组合 二项式定理为基础 加以推广 补充而 形成的一类组合问题 组合恒等式的证明要借助于高中常见的基础组合等式 例如 0 1 2 3210 210 1 1 11 1 n n n nnnn nn nnnn mr mn m n m n r n r n r n r n r n r n rn n r n CCCCC CCCC CCCC C r n C CCC CC 组合恒等式的证明方法有 恒等变形 变换求和指标 建立递推关系 数学归纳法 考虑组合意义 母函数 组合不等式组合不等式 组事不等式以前我们见的不多 在其他一些书籍中组合不等式的著述也很少 但是近 年来组合不等式的证明却出现在国内 国际大赛上 例如 1993 年中国高中数学联赛二试第二 大题为 设 A 是一个有 n 个元素的集合 A 的 m 个子集 A1 A2 Am两两互不包含 试证 1 m i A n I C 1 1 1 2 2 m i A n mC I 1 2 其中 Ai 表示 Ai所含元素的个数 表示 n 个不同元素取 Ai 的组合数 I A n C 再如 1998 年第 39 届国际数学奥林匹克竞赛中第二大试题为 在某一次竞赛中 共有 a 个参赛选手与 b 个裁判 其中 b 3 且为奇数 每个裁判对每 个选手的评分中只有 通过 或 不及格 两个等级 设 k 是满足条件的整数 任何两个 裁判至多可对 k 个选手有完全相同的评分 证明 2 1 b b a k 因此我们有必要研究组合不等式的证明方法 组合不等式的证明方法有 1 在集合间建立单射 利用集合阶的不等关系在集合间建立单射 利用集合阶的不等关系 定理 设 X 和 Y 都是有限集 f 为从 X 到 Y 的一个映射 1 若 f 为单射 则 X Y 2 若 f 为满射 则 X Y 2 利用容斥原理利用容斥原理 例如 设元素 a 属于集族 A1 A2 An 的 k 个不同集合 则在 k iii AAA 21 中 a 被计算了 k 次 当 k 2 时 集合两两的交集共有个 由于 n i i A 1 k iii AAA 21 2 k C 中至少少被计算了 k 1 次 这样我们得到下面 1 2 1 1 2 j nji ik AAak kk C 在故 的不等式 11 1 j nji ii n i i n i AAAA 组合不等式 可由容斥公式 删去右边第三个和式起的所有 1 1 1 11 1 i n i n j nji ii n i i n i AAAAA 和式得到 3 采用这种办法 我们可以从容斥公式得到另外一些组合不等式 只是要注意这些不等 式的方向的变化 3 利用抽屉原则利用抽屉原则 由于抽世原则的结论本身就是组合不等式关系 所以我们利用抽屉原则 巧妙构造抽 屉的方法证明组合不等式 4 利用组合分析利用组合分析 在复杂的组合计数问题 离散极值问题等问题中 会出现一些组合不等式 这时可运 用组合分析方法证明之 赛题精讲 例例 1 证明 n k nk n nn n C 0 12 2 2 2 2 分析 把 变换求和指标 n nk k n n nk k n n k k n n k k n CCCC 2 1 2 2 1 2 2 0 2 0 2 而对于变形为 证明 knjCCCCC n nk k n n nk k n n n nk k n n k k n n k k n 2 2 2 1 2 2 1 2 2 2 1 2 2 0 2 0 2 令对于和式 则 2 0 2 0 22 1 0 2 2 1 2 n n n k k n n j n n j n n j j n n nk k n CCCCCC 所以 2 2 0 2 2 0 2 n n n k k n n n k k n CCC 即 从而有 n n n n k k n CC 2 2 0 2 22 n k nk n nn n C 0 12 2 2 2 2 例例 2 求证 1 1 1 1 1 3 1 2 1 1 1 210 Nn Cnm C nm C m C m C m n nm n n n nnn 其中 证明证明 设 则由基本 n n n nnnn C nm C m C m C m a 1 1 1 3 1 2 1 1 1 210 4 恒等式得 r n r n r n r n r n C n r CCCC 11 11 及 1 1 1 3 1 2 1 1 1 1 1 1 2 2 1 1 1 1 1 2 1 0 1 1 1 0 n n n n n n n n nnnnnn C nm CC nm CC m CC m C m a 1 1 1 2 1 1 2 1 2 1 1 1 3 1 1 1 1 1 1 1 1 21 11 n nm n nnn nnnnnn Cnmmmnmnm n a mmmm a a mnmnm n a nmnm nn a nm n a aa n m aa n m aa 从而有 而 所以 即故 说明 注意到 an中各项的系数均与 n 无关 且符号正负相同 由此想到 an与 an 1 之间必定存在着某些联系 且是递推关系 例例 3 求证 n k k kn knk nC 0 12 22 1 2 1 分析 考虑到恒等式 仿例 2 解决 1 2212 k kn k kn k kn CCC 证明 令 n k k kn knk n Ca 0 12 22 2 1 因为 1 2212 k kn k kn k kn CCC 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 2 11 1 2 1 0 2 1 2 1 1 2 1 0 2 1 211 2 1 22 1 2 1 22 0 2 22 1 2 1 2 222 1 12 222 n r rn n r rnr r rn n r rnrk kn n k knk k kn n k knk n k k kn knk k kn n k k kn knkn n k k kn knkn n aC CC kr CC CC Ca 则令 所以 5 令 n k nnnn k kn knk aabbC 0 12 22 2 1 则 4 2 1 4 1 2 1 2 1 2 1 2 11 1 0 1 2 2 1 2 1 1 12 1 1 12 222 1 1 2 222 nn n j j jn jnj n nk kn n k k kn knkn n k nk kn knkn n ba Ca CC Cb又 于是由 式得 122111211 2 4 nnnnnnnnnnn aaaaaaaaaab即从而推知 这说明 an 为等差数列 而 a0 1 a1 2 故公差 d 1 且 an n 1 说明 此题运用变换求和指标的方法 找出了 an an 1 an 2之间的线性关系式 再由 初始条件求得 an 这种利用递推关系求组合数的方法 在解决较复杂的计算或证明组事恒等 式时经常用到 例 11 设是集合 M 的两个划分 又对任 212211nn BBBDAAAD 何两个不变的子集有求证 并说明等号能否 1 njiBA ji nBA ji 2 2 1 nM 成立 证明 令 不妨设因两两不 1 min njiBAk ji kAi n BBB 21 交 故中至多有个使 设 n BBB 21 k j B j BA1 j BA1 2 1 knmj 由的选取知从而 k 2 1 mjkBj 1 mkB m j j 又因 j BA1 1 nmi 故 11 nBABA ii 即 knBi 所以 111 knmnmkBBBM n mj j m j j n j j 6 2 knmknn 若因故 2 n k km 2 2 2 2 2 2 2 2 2 2 n k nn knkknnknmknnM 若则 从而 2 n k 2 1 2 ni n Ai 2 2 11 n AAM n i i n i i 下面说明是可以取到的 显然这时为偶数 取则 令 2 2 n M n 4 n8 M 易验证 M 的两个划分 8 7 6 5 4 3 2 1 M D1 1 2 3 4 5 6 7 8 D2 1 2 3 5 4 6 7 8 满足题目条件 例 12 设是正整数 我们说集合 1 2 2 的一个排列 nn n xxx 221 具有性质 P 是指在 1 2 2 1 当中至少有一个 使得求证 对于ni 1 nxx ii 任何 具有性质 P 的排列比不具有性质 P 的排列的个数多 n 1989 第 30 届 IMO 试题 6 证明 设 A 为不具有性质 P 的排列的集合 B 为具有性质 P 的排列的集合 显然 为了证明 只要得到就够了 使作容斥原理 2 nBA BA 2 2 1 nB 设 中 与相邻的排列的集合为则 n xxx 221 knk 2 1 nkAk 由容斥原理得 12 2 nxAk 1 22 2 2 njknxAA jk 22 4 12 2 2 11 nCnnAAAB n njk jk n k k 22 2 22 1 2 2 nnnnnnn 2 2 1 22 2 12 2nn n n 例 13 平面上给定个点 其中任何三点不共线 任意地用线段连接某些点 这些线n 段称为边 则确保图形中出现以给定点为顶点的阶完全图的条件是图形中的边 nmm 的条数 1 1 2 2 2 m n m m n C CC x 7 证明 构造抽屉 每个抽屉里有个相异点 共可得个抽屉 又由于同一条边会m m n C 在个抽屉里出现 根据抽屉原则知 当时 才能确保有一 2 2 m n C1 1 22 2 m m n m n CCCx 个抽屉里有条边 而这条边恰好与其中不共线的相异点构成一个阶完全图 2 m C 2 m Cmm 这就是说 确保图形中出现阶完全图的条件是其中边的条数m 1 1 2 2 2 m n m m n C CC x 评述 完全图 是图论中的基本概念 此处从略 例 14 设为实数 满足求证 对于每一整数 n xxx 21 1 22 3 2 2 2 1 n xxxx 存在不全为零的整数使得并且2 k 21n aaa 3 2 1 1 nikai 1987 年第 28 届 IMO 试题 3 1 1 2211 n nn k nk xaxaxa 证 由柯西不等式得 111 22 3 2 2 2 1 2222 21nn xxxxxxx 即 21 nxxx n 所以 当时 有10 kai 1 1 212211 nkxxxkxaxaxa nnn 把区间 0 等分成个小区间 每个小区间的长度 由于每nk 1 1 n k 1 1 2 k nk 个能取个整数 因此 i ak 2211nn xaxaxa 共有个正数 由抽屉原则知必有二数会落在同一小区间内 设它们分别是 n k 与 因此有 n i ii xa 1 1 n i ii xa 1 1 2 1 k nk xaa n i iii 很明显 我们有 现在取 2 1 1 nikaa ii 0 0 ii iii i xaa xaa a 如果 如果 8 这里于是 可表示为这里为整数 适合 2 1ni 1 1 1 n n i ii k nk xa i a 2 1 1 nikai 例 15 设 A 是一个有个元素的集合 A 的个子集两两互不包含 试nm m AAA 21 证 1 2 1 1 1 m i A n i C 2 1 mC m i A n i 其中表示所含元素的个数 表示个不同元素取个的组合数 i A i A i A n Cn i A 1993 年 全国高中数学联赛二试第二大题 分析 若 1 式已证 由柯西不等式立即可得 2 式 因此 关键是证 1 式 又据组合公式知 1 式等价于 所以我们用组合的方法来证明不等式 1 nAnA i n i i 证明 1 对于 A 的子集我们取补集 21 i Ai xxxA 并取的元素在前 元素在后 作排列 21 i Ani yyyA i A i A 这样的排列共有个 21 i A xxx 21 i An yyy ii AnA 显然 中每一个排列 也是 A 中的一个排列 若时 对应的排列与对庆的排ij j A i A 列互不相同 则所对应的排列总数便不会超过 A 中排列的总数现假设 m AAA 21 n 中对应的某一排列 j A 21 j A xxx 21 j An yyy 与 中对应的某一排列 相同 指出现的元素及元素位置都相同 则当 i Aij 时 当时 这都与两两互不包 ij AA ij AA ij AA ij AA m AAA 21 含 矛盾 由于对应的排列对 互不相同 而 A 中个元素的全排列有 个 故 m AAA 21 nn 得 9 即 1 nAnA i n i i 1 1 1 n i A n i C 2 由上证及柯西不等式 有 1 1 2 11 2 1 1 m C CC m i m i A n m i A n m i A n i ii 评述 本题取自著名的 Sperner 定理 设 Z 为元素 为 Z 的子集 互不包含 则的最大值为 n m AAA 21 m 2 n n C 例 16 设 S 0 1 2 N2 1 A 是 S 的一个 N 元子集 证明存在 S 的一个 N 元 子集 B 使得集合 A B 中的元素模 N2的余数的数目不少于 S 中元素的 BbAaba 一半 第 40 届 IMO 预选 题 证明 设 X 为子集中元素