nbhkdz.com冰点文库

数学竞赛讲义组合7-21


第七讲 组合综合问题
本讲概述
在前六讲我们对组合数学中的不少专题进行了研究,本讲不再进行具体某个专题的学习,而是通过 一些综合性的问题的探讨来寻找组合数学“解题的感觉”.本讲的题目与前面相比,综合性更强,难度在 二试与冬令营之间,可能需要综合应用前面所学的多种组合知识乃至其它学科的知识来解决. 事实上,组合与几何学、数论相联系形成的组合几何、组合数论问题往往

难度较大,又能同时考察 多个学科,是命题人青睐的对象,而在组合问题的探索过程中,特别是组合极值问题中,常常用到代数 知识特别是数列与不等式知识. 教师备注:本讲主要研究两大方面问题: (1)组合与其它学科相结合 (2)组合极值及其构造、论 证; 部分题目来自冬令营或相当冬令营难度的比赛,教师可自行选择适当问题讲述

只有 15 没有配对,这就是乙队. 于是乙队赛过 15 场. 【例3】 20 支足球队参加比赛,每两队至多赛一场.为了使任何三队中都有两队赛过,球赛组委会安排了 m 场比赛,试求 m 最小值. 【解析】 设 A 队赛过 k 场,是所有队中赛过场次最少的.与 A 队赛过的 k 个队,各至少赛过 k 场,没有与 A 赛过的 19-k 个队中的任何两队 B,C 必赛过(否则就出现 A,B,C 三队两两未赛过,矛盾! ). 于是比赛场数 m ?

1 2 2 k (k ? 1) ? C19 ? k ? ? k ? 9 ? ? 90 ? 90 , 2
2

于是至少要赛 90 场. 下面给出一种比赛方案,使得恰赛 90 场: 把 20 支队分成两组,每组 10 个队,同组两两都赛,不同组不比赛,共安排 2C10 场比赛. 显然这个方案合要求.

注 本题为组合中最难的安排赛程表题型,也可以把它看成一个图论问题 .比赛方案是受到论证过程的结 果启发构造出来的. 【例4】 设 k , n 为给定的整数, n ? k ? 2 . 对任意 n 元的数集 P ,作 P 的所有 k 元子集的元素和,记
这些和组成的集合为 Q ,集合 Q 中元素个数是 CQ ,求 CQ 的最大值.
k 【解析】 CQ 的最大值为 Cn .

例题精讲
【例1】 设 ABC 为正三角形,E 为线段 BC,CA,AB 上点的集合(包括 A,B,C 在内) 。将 E 分成两 个子集,求证:总有一个子集中含有一个直角三角形的顶点。

因 P 共有 Cn 个 k 元子集,故显然有 CQ 下面我们指出,对集合 P ? {2,

k

k . ? Cn
k ,即 P 的任意两个不同的 k , 2n},相应的 CQ 等于 Cn k

22 ,

元子集的元素之和不相等. 从而 CQ 的最大值为 Cn . 事实上,若上述的集合 P 有两个不同的 k 元子集

A ? {2r1 , 2r2 ,
【解析】 将 E 中的点染成红、蓝二色,即证明必存在一个直角三角形,它们的顶点同色。 在三边上取三等分点 P,Q,R,如图 01—05。易知 RQ⊥BC,QP⊥AC,PR⊥AB。这三点必至少有 两点同色。不妨设 R,Q 为红色。 (1)如果 BC 边上除 Q 点外还有红色的点 X, 则 Rt△RQX 三个顶点同为红色。 (2)如果 BC 边上除 Q 外不存在红色点, 则 B 点是蓝色的。如果 AB 上除 B 外还有蓝色点 Y, 作 YM⊥BC,M 为垂足,显然 M 不同于 Q。 所以 Rt△YBM 三个顶点均为蓝色; 如果 AB 上除 B 点外均为红色。作 QZ⊥AB,Z 为垂足, 则 Rt△RQZ 的三个顶点均为红色。证毕。 【例2】 某足球邀请赛有 16 个城市参加,每市派出甲乙两队.根据比赛规则,每两队之间至多赛一场, 且同一城市两队之间不比赛.比赛进行若干天后统计,发现除 A 市甲队之外,其它各队已赛过场 次互不相同.试问 A 市乙队已赛过多少场? 【解析】 依 比 赛 规 则 , 每 队 至 多 赛 30 场 , 所 以 除 A 市 甲 队 之 外 , 其 它 各 队 已 赛 过 场 次 依 次 为
使得

, 2rk } ,

B ? {2s1 , 2s2 ,
? 2sk ? M

, 2sk },
(设).

A 与 B 的元素之和相等,则

2r1 ? 2r2 ?

? 2rk ? 2s1 ? 2s2 ?



因①可视为正整数 M 的二进制表示,由于 ri 互不相同, si 互不相同,故由正整数的二进制表示的唯 一性,我们由①推出,集合 {r 1 , r2 , 这就证明了我们的断言.

, rk } 必须与 {s1, s2 ,

, sk } 相同,从而子集 A ? B ,矛盾.

注 本题为 2009 江苏赛区复赛题. 这是一道典型的组合极值问题,难度并不太大. 这种问题一般分为两部 分:构造与论证,分别考察不同的数学能力,因此是近年来的命题热点. 【例5】 (1) 若 n (n ? N*) 个棱长为正整数的正方体的体积之和等于 2005, 求 n 的 最小值, 并说明理由; (2) 若 n (n ? N*) 个棱长为正整数的正方体的体积之和等于 2002 最小值, 并说明理由.
3 3 3 3 【解析】 (1) 因为 10 ? 1000, 11 ? 1331, 12 ? 1728, 13 ? 2197 , 12 ? 2005 ? 13 ,
3 3
2005

, 求 n 的

0,1, 2, ???, 29,30 .考场赛过

30 场和 0 场的队,经简单推理知此两队必为同城队;接下来依次配对(29,1) ,

(28,2) ,?, (14,16).
高一·联赛班·寒假第 7 讲·教师版

1

故 n ? 1.
3 3 3 3 因为 2005 ? 1728 ? 125 ? 125 ? 27 ? 12 ? 5 ? 5 ? 3 ,所以存在 n ? 4 , 使

????? 21 分 ⑤ 式模 9 , 由 ⑥、⑦ 可知, n ? 4 . 而 2002 ? 10 ? 10 ? 1 ? 1 ,则
3 3 3 3

nmin ? 4 .

?????? 6 分

20022005 ? 20022004 ? (103 ? 103 ? 13 ? 13 ) ? (2002668 )3 ? (103 ? 103 ? 13 ? 13 ) ? (2002668 ?10)3 ? (2002668 ?10)3 ? (2002668 )3 ? (2002668 )3 .?? 24 分
因此 n ? 4 为所求的最小值. 注 本题为 2005 年江苏预赛 16 题. 这类与数论相联系的极值问题往往兼具组合构造与数论证明两大特点 但鉴于本题组合味道并不太浓,建议选讲. 【例6】 假定 100 个人中的每一个人都知道一个消息,而且这 100 个消息都不相同。为了使所有的人都 知道一切消息,他们一共至少要打多少个电话? 【解析】 198 个。 考虑一种特殊的通话过程:先由 99 人每人打一个电话给 A,A 再给 99 人每人打一个电话,这样一共 打了 198 个电话,而且每人都知道了所有的消息。 下面我们说明这是次数最少的。考虑一种能使所有人知道一切消息的通话过程中的关键性的一次通 话,这次通话后,有一个接话人 A 知道了所有的消息,而在此之前还没有人知道所有的消息。 除了 A 以外的 99 人每人在这个关键性的通话前, 必须打出电话一次, 否则 A 不可能知道所有的消息; 又这 99 人每人在这个关键性的通话后,又至少收到一个电话,否则它们不可能知道所有的消息。 注 本题也是一道组合极值问题 【例7】 在 n 个元素组成的集合中取 n ? 1 个不同的三元子集。证明:其中必有两个,它们恰有一个公共元。 【解析】 证明:设结论不真。则所给的 3 元子集要么不交,要么恰有两个公共元,如果子集 A 与 B 恰有 两个公共元,则记 A B 。设 A,B,C 是三个子集。可以证明如果 A B, B C 则 A C ,于是所有给定 的 3 元子集可以分类,使得同一类中任意两个不同子集都恰有两个公共元。而不同类的子集不相交。于是对每 个子集类,有三种可能: (1)恰含 3 个元素的类。 (2)恰含 4 个元素的类。 (3)至少含 5 个元素的类。 在(1)下,3 元子集类恰由一个 3 元子集组成。 在(2)下,子集类中至多有 4 个子集。 考虑(3) 设 A ? {a, b, c}, B ? {a, b, d} ,则还有一个 e,由 A 对子集类中任意子集 D,由 A

3 3 若 n ? 2 ,因 10 ? 10 ? 2005 , 则最大的正方体边长只能为 11 或 12 ,计算

2005 ?113 ? 674, 2005 ?123 ? 277 ,而 674 与 277 均不是完全立方数, 所以
n ? 2 不可能是 n 的最小值.
?????? 9 分

2 3 若 n ? 3 ,设此三个正方体中最大一个的棱长为 x , 由 3x ? 2005? 3 ? 8 , 知

最大的正方体棱长只能为 9 、 10 、 11 或 12 .
3 3 3 3 由于 2005? 3 ? 9 , 2005? 2 ? 9 ? 547, 2005? 9 ? 2 ? 8 ? 0 , 所以 x ? 9 .

由于 2005? 2 ? 10 ? 5 , 2005 ? 10 ? 9 ? 276 , 2005 ? 10 ? 8 ? 493 ,
3
3 3 3 3

2005? 103 ? 2 ? 7 3 ? 0 , 所以
3 3

x ? 10 .
3 3

由于 2005 ? 11 ? 8 ? 162 , 2005 ? 11 ? 7 ? 331 , 2005? 11 ? 2 ? 6 ? 0 ,
3 3

所以 x ? 11 .
3 3 3 3 3 由于 2005 ? 12 ? 6 ? 61, 2005 ? 12 ? 5 ? 152 ? 5 , 所以 x ? 12 .

因此 n ? 3 不可能是 n 的最小值. 综上所述, n ? 4 才是 n 的最小值. (2) 设 n 个正方体的棱长分别是 x1 , x2 ,
3 3 x1 ? x2 ?

?????? 12 分

C, B C ,有 C ? {a, b, e} 。因此

, xn , 则

D, B

D, C

D 它包含 a,b,于是类中子集个数比类中元素个数少 2,于

3 ? xn ? 20022005 .????? ⑤

3 由 2002 ? 4(mod9) , 4 ? 1(mod9) ,得

是,每个类中子集个数不超过元素个数,但是题中条件子集数大于元素个数,矛盾! 注 本题为一道美国竞赛题,有高等数学的背景 a2 , , an } ,其中诸 ai ? R ,ai ? ai ?1 . 作 【例8】 设 n 为大于等于 2 的某个确定的正整数,集合 A ? {a1 , ?? 15 分 数的个数. 3} 时, ? ? A? ? 3 . 例如 A ? {1,2} 时, ? ? A? ? 1 ; A ? {1 ,2 ,
2, 22 , 23} 时,求 ? ? A? (Ⅰ) A ? {1,

2 和 ai ? a j ?1≤ i ? j ≤ n ? ,共有 Cn 个和,其中有些可能是相同的. 称 ? ? A? 为这些和中互不相同的

20022005 ? 42005 ? 4668?3?1 ? (43 )668 ? 4 ? 4(mod9) .?? ⑥
又当 x ?N* 时, x ? 0, ?1 (mod9) ,所以
3

(Ⅱ)当 n ? 5 ,且 a1 ~ a 5 恰构成 a1 ? 1 , d ? 2 的等差数列时,求 ? ? A? ;
3 1 3 2 3 3

≡ 4(mod 9) , x ? x ≡ ∕ 4 (mod9) , x ? x ? x ∕ ≡ 4 (mod9) . ? ⑦ x ∕
3 1 3 1 3 2

高一·联赛班·寒假第 7 讲·教师版

2

2 【解析】 (Ⅰ)易得的不同的和有:3,5,9,6,10,12,共 6 个,∴ ? ? A? ? 6 ……2 分

(Ⅲ )试证明 2n ? 3 ≤ ? ? A ? ≤

n ? n ? 1?

? ? 2k 2 ? k ? ?
2

l ? k ?1

? 2k ?? ? ?

2k

2

2 2 ? k ? ? ? 2k 2 ? l ? ? ? ?



③ 右?

3, 5, 7, 9} ,由 1 ? 3 ? 1 ? 5 ? 1 ? 7 ? 1 ? 9 ? 9 ? 3 ? 9 ? 5 ? 9 ? 7 (Ⅱ) A ? {1, 知 ? ? A? ≥ 7 ,又 3 ? 5 ? 1 ? 7 , 3 ? 7 ? 1 ? 9 , 5 ? 7 ? 9 ? 3

l ? k ?1

?? ?k

2k

2

? 2k ? 2k 2 ? l ? ? ?
2k

∴ ? ? A? ? 7 …………………………………………………..……………..5 分 (Ⅲ)⑴ 我们来证明 ? ? A?min ? 2n ? 3 由 a1 ? a2 ? a1 ? a3 ?
? a1 ? an ? a2 ? an ? ? an ?1 ? an (以上共 2 n ? 3 个)知

? k ? 4k 3 ? k 2 ? ? 2k ? ? l
k ?1

? 4k 4 ? k 3 ? 2k ?
4 3 2

k ?? ?? k ? 1? ? 2k ? ? 2
2

? ? A? ≥ 2n ? 3 .

? 4k ? 4k ? k ? k

? 2k ? 1?

2

?左

取 A ? {1,2 , ,n} , ak ? k ? k ? 1, 2, , n?

从而③成立 ? ②成立,故猜想成立.………………14 分 备选 2 给出项数为 n ? 1 的的数列 {ak } :1 ? a1 ≤ a2 ≤ ≤ an?1 ? t ,诸 ai 为正整数,且 a1 ? ? an?1 ? 2n , 取 n ? 1 个砝码,重量恰为 a1 ,…, an ?1 克,由重而轻地逐个把砝码放到天平上, (先从左开始放) ,每次都 放在较轻的盘中, (两边相等时可放入任一盘中) (Ⅰ )当 n ? 5 时,试适当选取恰当克数的砝码,并给出左盘、右盘砝码和的差值 ? (Ⅱ )设 a1 ? ? am ? 1 ? am?1 ,试证: m ≥ t (Ⅲ )证明:放完所有 n ? 1 个砝码时天平恰好平衡. 解析: (Ⅰ ) n ? 5 时,共有 6 个砝码,重量和为 12,取 a1 ? a2 ? a3 ? 1 , a4 ? 2 , a5 ? 3 , a6 ? 4 , 则左盘放 4 →右放 3 →右放 2 →左放 1 →左、右各放 1 ∴左盘放 4,1,1,右盘放 3,2,1 ? ? ? 4 ? 1 ? 1? ? ?3 ? 2 ? 1? ? 0 ………………………………………………….3 分 (Ⅱ )由题意 n ? 1 个砝码中有 m 个为 1 克的,最重的一个为 t 克, 反设 m ? t ,则 t ≥ m ? 1 ; 其余的砝码个数为 ? n ? 1? ? 1 ? m ? n ? m 个,每个的重量 ≥ 2 克. ∴砝码总重量 Sn?1 ≥ m ?1 ? ? n ? m ? ? 2 ? 1? t
? 2n ? m ? t ≥ ? 2n ? m? ? ? m ? 1? ? 2n ? 1 ? 2n (克)

则 ai ? a j 取遍从 1 ? 2 ? 3 到 ? n ? 1? ? n ? 2n ? 1之间所有的值,此时恰有 ? ? A? ? 2n ? 3 . ⑵ 来证 ? ? A?max ? C .
2 n

…………10 分
2 n

显然当诸 ai ? a j ?1≤ i ? j ≤ n ? 互不相等时,共有 C 种取法. 我们举例说明可以取到.仿(Ⅰ)取 A ? {1, 2, 22 , 23, , 2n?1} 用反证法,反设存在 i , j , k , l ?{1,2 , ,n} 使 ai ? a j ? ak ? al ,其中 i ? j , k ? l 即 2i ?1 ? 2 j ?1 ? 2k ?1 ? 2l ?1 ,易得 l ? j ,进一步可得 k ? i .可见不存在两个和相等.
2 于是对 Cn 个二元组( i , j ) , ai ? a j 总两两不同.……………………………..14 分

注 本题为讲义作者根据美国数学奥林匹克试题改编 2, , 2k ? . 备选 1:设 k 为给定的自然数,取数列 {an } 为 a1 ? 2k 2 ? k , at ?1 ? at ? 1?t ? 1,
a2 , , a2k ?1} . 取集合 M ? {a1 , (Ⅰ)当 k ? 1 时,求 M ,并把 M 中数分为两组,分别构成现为集合 A , B . 使 ? x2 ? ? y 2 . ①
x? A x?B

(Ⅱ)对 k ? 2 时作上述操作. (Ⅲ)对一般的 k ? N ? ,试问是否仍存在上述分拆,使①成立? 5} ,有 32 ? 42 ? 52 ……………………………...2 分 解析: (Ⅰ) k ? 1 时, M ? {3 ,4 , 11, 12 , 13 , 14} ,有 (Ⅱ) k ? 2 时, M ? {10 ,
2 2 2 2 ? 102 ? 112 ? 122 ? 132 ? 142 ? 102 ? ? ??13 ? 11 ? ? ?14 ? 12 ??

这与 Sn?1 ? 2n 相矛盾! ∴假设不成立,故必有 m ≥ t .……………………………………………..8 分 (Ⅲ )∵最重的一个为 t 克,∴天平两边重量之差始终 ≤ t 克. 在放 m ?≥ t ? 个 1 克的砝码前也同样如此.………………………………..11 分 以下说明:不会出现最终两边恰相差 1 克的情况. 这是因为若如此,则左、右盘重量和 S n ?1 为奇,这与 Sn?1 ? 2n 为偶矛盾! 将重为 1 的砝码逐一放上去,显然可以实现平衡.证毕.………………14 分 【例9】 如图,正五边形上的顺次排列 5 个整数 x1 , x 2 ,…, x5 ,其和是正的,对其中任意 3 个连续顶点 上的数 x , y , z ,若中间的 y ? 0 ,则作变换 ( x, y, z ) ? ( x ? y, ? y, y ? z ) ,只要所得 5 个整数中仍有负 的,则继续进行此调整. 试证:这种调整只能进行有限次. x5 x1 【解析】 设 当 x1 ? 0 时,对 ? x5 ,x1 ,x2 ? 作变换,
? 2x1 ? x1 ? x2 ?
高一·联赛班·寒假第 7 讲·教师版

? 102 ? 2 ? ?11 ? 12 ? 13 ? 14? ? 2 ? ?50 ? 50? ? 0 ……….…5 分

(Ⅲ)由前两问之方法猜想可能有: a2 , , ak , ak ?1 , a2k ?1} 有 对一般的 M ? {a1 ,

a12 ?

2 2 ? ak ?1 ? a k ? 2 ?

2 ? a2 k ?1 后k个



前k ?1个

a2 , , ak ?1} , B ? {ak ? 2 , , a2k ?1} 即可使使①成立…8 分 如②成立,则取 A ? {a1 , 下证②:

f ? x1 , , x5 ? ? ? x1 ? x3 ? ? ? x2 ? x4 ? ? ? x3 ? x5 ? ? ? x4 ? x1 ? ? ? x5 ? x2 ?
2 4 2 2

2

② ? ? ? 2k ? l
2 l ?k

2k

2

? ? ? ? 2k
l ? 2 k ?1

3k

2

? l?

2

f ? ? x1 ,x1 ? x2 ,x3 ,x4 ,x5 ? x1 ? ? f ? x1 ,x2 ,x3 , x4 , x5 ?

x2 x3

x4

? x5 ? ? 0

3

可见 f ? x1 , ,x5 ? 在每次调整后总单调严格递减, 每次最少减少 2, 而由 f 表达式知 f 恒为非负, 故对 f 的调整必在有限次内终止. 注 本题为 27 届 IM0 试题,本题所用的方法为构造目标函数法 备选 3 已知整数 m, n 满足 m, n ? {1,2,?,1981 }及 (n 2 ? mn? m2 ) 2 ? 1 ,求 m ? n 的最大值.
2 2

最后,对于和为 1995 的不同分拆,S 的最小值在 xi=11-i (2≤i≤10)时达到.事实上,反设 k 是使此式不 成立的最大 i,即 xk>11-k,而 i>k 时有 xi=11-i,将 x1,xk 分别改为 x1+1, xk-1,所得各数仍两两不同.由于 x1 的两个相邻数(x10,x9)是最小的两数,故调整后 S 变小,矛盾. 因此,和数最小的数组是 1950,1,9,3,7,5,6,4,8,2.最小值是 1950+9+27+21+35+30+24+32+16+3900=6044. 注 本题为调整法的经典应用,是 1995 年 CMO 试题 【例11】 对于整数 n ≥4,求出最小的整数 f ( n) ,使得对于任何正整数 m ,集合 ?m, m ? 1,...,m ? n ? 1? 的任 一个 f ( n) 元子集中,均有至少 3 个两两互素的元素. 【解析】 取 m=2,由容斥原理,集合{2,3,…,n+1}中被 2 或 3 整除的数的个数为

【解析】 若 m ? n ,则 m ? n ? 1 ,若 m ? n ,由 n ? m n ? m ? ?1
2 2

n ? m ? mn ? 1 ? m ,得 n ? m .
2 2 2

因为

(n 2 ? mn? m2 ) 2

? (n ? m) 2 ? m(n ? m) ? m 2

?

? ?

2

? m 2 ? m(n ? m) ? (n ? m) 2 ,
于是, 若 (m, n) 满足条件; 则 (n ? m, m) 也满足条件.由于 n ? m , 可从 (n, m) 出发, 并降得到 (1,

?

2

? n ? 1? ? n ? 1? ? n ? 1? . ? ? ? ? 2 ? ? ? ? 3 ? ? ? ? 6 ? ?
这些数中的任意 3 个或有 2 个同被 2 整除,或有 2 个同被 3 整除,不会两两互素.因此 f(n)≥ ?

}的全部 1) ,反之亦成立,即由(1,1)出发,利用 (n ? m, m) ? (m, n) 可得到满足 m, n ? {1,2,?,1981
解.即 (1,1)→(1,2)→(2,3)→(3,5)→(5,8)→(8,13)→(13,21)→(21,34)→ (34,55)→(55,89)→(89,144)→(144,233)→(233,377)→(377,610)→(987,1597) 因此,所求 m ? n 的最大值为 987 +1597 =3524578 注 本题为选讲
2 2
2 2

? n ? 1? ? n ? 1? ? n ? 1? ? n ? 1? ? n ? 1? ? n ? 1? +1. 记 +1=kn. ? ? ? ? ? ? 2 ? ? ? ? 3 ? ? ? ? 6 ? ? ? 2 ? ? ? ? 3 ? ? ? ? 6 ? ?

下证对任何正整数 m ,集合 ?m, m ? 1,...,m ? n ? 1? 的任一 kn 元子集中,均有至少 3 个两两互素的元素. 从而得出 f(n)= ?

? n ? 1? ? n ? 1? ? n ? 1? +1. ? ? ? 2 ? ? ? ? 3 ? ? ? ? 6 ? ?

【例10】 设 a1, a2, ... , a10 是 10 个两两不同的正整数,它们的和为 1995, 试求 a1a2+a2a3+...+a9a10+a10a1 的最小值。 【解析】 先取定正整数 x1>x2>…>x10,将它们沿圆周顺时针排成 a1,…,a10 使 S= 不妨设 a1=x1,a2<a10.则必是 x1,x10,x2,x8,x4,x6,x5,x7,x3,x9. 用调整法依次证明如下: 1).反设 a2=xi (i≤9),aj=x10(3≤j≤9).将顺时针 a2,…,aj 段反序,其它不变,得到新的排列,二者和数之差 S -S′=x1xi+x10aj+1-x1x10-xi aj+1=(x1-aj+1)(xi-x10)>0,与 S 最小矛盾.故 a2=x10. 同样,若 a10=xi (i≤8), aj=x9(3≤j≤9).将顺时针 aj,…,a10 段反序,其它不变,得到新的排列,二者和数之差 S -S′=aj-1x9+xix1-aj-1xi-x9x1=(x1-aj-1)(xi-x9)>0,矛盾.故 a10=x9. 2).一般,可以用同样的整段反序调整法证明:将 x1>…>xk 排成 y1,…,yk 使得 ay1+y1y2+…+yk-1yk+ykb 最小,则当 a>b>x1 时必 y1= xk, yk=xk-1,而当 xk>b>a 时必 y1=x1,yk=x2.从而得到上述结论.
10

?a a
i ?1

i i ?1

(a11=a1).最小.

(1).首尾为奇数的 3 个接连整数 2u+1,2u+2,2u+3 两两互素;因此,4 个接连整数中必有 3 个两两互素. (2).{a,a+1,…,a+5}的任一 5 元子集 A 中必有 3 个元素两两互素.事实上,若不属于 A 的数 b 是 a,a+1,a+4,a+5 之一,则 A 中有 4 个接连整数;若 b 为 a+2,a+3 中的偶数,则 A 中有首尾为奇数的 3 个接连整数. 若 b=a+2 为奇数,则 a 为奇数, (a,a+4)=(a,a+1)=(a+3,a+4)=1, 又 (a,a+3)=(a,3) 和 (a+1,a+4)=(a+1,3) 等于 1 或 3 且二者不能同时等于 3, 故 (a,a+1,a+4)和(a,a+3,a+4)中至少有一组两两互素.同理当 b=a+3 为奇数时(a+1,a+2,a+5)和(a+1,a+4,a+5)中至 少有一组两两互素. (3).设 n=6q+r,任意 n 个接连整数可分为 q 个接连 6 数段 Ii 和一个接连 r 数段 R(r=0 时此段为空).列 出 r=0,1,…,5 时对应的 kn 值: r 0 1 2 3 4 5 kn 4q+1 4q+2 4q+3 4q+4 4q+4 4q+5 由此可知,任一 kn 元子集或者含有某个段 Ii 中的 5 个数,或者含有段 R 中的 4 个接连数,由(2),其中必有 3 个 元素两两互素. 注 本题为 2004 年全国联赛二试最后一道,难度较大

大显身手
1. 设 a1 , a2 , a3 , a4 是 1,2,3,4 的任一排列, f 是 {1,2,3,4} 到 {1,2,3,4} 的映射,且满足 f (i) ? i ,记数

高一·联赛班·寒假第 7 讲·教师版

4

a2 ?a1 表? ? f (a1 ) f(a2 )

a3

? 。 若数表 M , N 的对应位置上至少有一个不同, 就说 M , N 是 f ( a3 ) f ( a 4 ) ? ? a4
(D)576

的格子中填的数大于有“*”的格子中任何一个数,所以棋盘上没有“*”的格子都为“优格” ,共有

n(n ? 2004) 个。
此时每行有 2004 个格子有“*” ,每列也有 2004 个格子有“*” (如图) 。实际上,当1 ? i ? 2003 时, 第 i 列的第 1、2、…、i、n+i-2003、n+i-2002、...、n 行中有“*” 。当 i ? 2004 时,第 i 列的第 i-2003、 i-2002、...、i 行中有“*” 。所以每行有 2004 个格子有“*” ,每列也有 2004 个格子有“*” (如图) * * * * * * * * * * * * * * * * * * * * * * * *

两张不同的数表。则满足条件的不同的数表的张数为 (A)144 (B)192 (C)216 列,所以满足条件的数表共有 24 ? 9 ? 216 张,故选 C。 注 本题为 2005 年四川预赛题

4 【解析】 对于 a1 , a2 , a3 , a4 的一个排列,可以 9 个映射满足 f (i) ? i ,而 a1 , a2 , a3 , a4 共有 A4 ? 24 个排

在正 2006 边形中,与所有边均不平行的对角线的条数为( C (A) 2006 (B) 10032 (C) 10032 ? 1003

) 。

(D) 10032 ? 1002.

1 ? 2n ? (2n ? 3) ? n(2n ? 3) 条。 2 计算与一边 A1 A2 平行的对角线条数,因 A1 A2 // An?1 An?2 ,与 A1 A2 平行的对角线的端点只能取
【解析】 正 2n 边形 A1 A2 ? A2n ,对角线共有

自 2n-4 个点,平行线共 n-2 条。故与某一边平行的对角线共 n(n-2)条。由此可得与任何边都 不平行的对角线共有 n(2n-3)-n(n-2)=n(n-1)条。 因此正确选项是 C。
注 本题为 2006 浙江预赛题 2. 将 n2 个互不相等的数排成下表: a11 a21

a12 a22

a13 ? a1n a23 ? a2n

所以棋盘中“优格”个数的最大值是 n(n ? 2004) 。 注 本题为首届东南 MO 试题-4 4. 某中学某班 48 位同学来自全省各地,原来并不全部相识。 (1)开学一星期后,每位同学都恰好认识了班上其他 11 位同学。是否一定存在这么 5 个人,他们之

an1 an2 an3 ? ann 先取每行的最大数,得到 n 个数,其中最小数为 x;再取每列的最小数,也得到 n 个数,其中最大数 为 y。试比较 x 和 y 的大小。 【解析】 先讨论 n=3 的情况,任取两表: 1 3 7 1 2 3 2 5 6 4 5 6 8 9 4 7 8 9 左上表中 x=6,y=4;右上表中 x=3,y=3。两个表都满足 x≥y,所以可以猜想 x≥y。 对一般情况,设 x 是第 i 行第 j 列的数 a(i,j) ,y 是第 l 行第 m 列的数 a(l,m) 。考虑 x 所在的行与 y 所在的列交叉的那个数,即第 i 行第 m 列的数 a(i,m) 。显然有 a(i,j)≥a(i,m)≥数 a(l,m) , 当 i=l,j=m 时等号成立,所以 x≥y。 3. 给定大于 2004 的正整数 n,将 1、2、3、…、 n 分别填入 n×n 棋盘(由 n 行 n 列方格构成)的 方格中,使每个方格恰有一个数。如果一个方格中填的数大于它所在行至少 2004 个方格内所填的数,且 大于它所在列至少 2004 个方格内所填的数,则称这个方格为“优格” 。求棋盘中“优格”个数的最大值。 【解析】 为叙述方便,如果一个方格中填的数大于它所在行至少 2004 个方格中所填的数,则称此格为行 优的。 由于每一行中填较小的 2004 个数的格子不是行优的, 所以每一行中有 n-2004 个行优的。 一个方格为“优格”一定是行优的,所以棋盘中“优格”个数不大于 n(n ? 2004) 。
2

间两两都不相识?请证明你的结论; (2)开学一个月后,每位同学认识班上其他同学都超过 36 人。是否一定存在这么 5 个人,他们之 间两两都相识?请证明你的结论。 【解析】 ⑴ 不一定. 下面给出一个反例: 48 位同学分别分在 4 个宿舍,每个宿舍 12 人。一星期后,同宿舍的同学相互相识,若每个人都不认 识其他宿舍的人,则班上任意的 5 个人,根据抽屉原理,总有两个人在同宿舍,同宿舍的两个人相互认识。 ⑵ 一定存在. 设 a 是班上的同学,集合 A 是与 a 相识的同学组成的集合,则 card(A)>36,从中找一个同学 b, 集合 B 是与 b 相识的同学组成的集合,card(B)>36, 且 card(A∩B)= card(A)+card(B)-card(A∪ B)>36+36-48=24; 在集合 A∩B 中找一个同学 c,集合 C 是与 c 相识的同学组成的集合,card(C)>36, 则 card(A∩B∩C)= card(A∩B)+card(C)-card(A∩B∪ C)>24+36-48=12. 在集合 A∩B∩C 中找一个同学 d,集合 D 是与 d 相识的同学组成的集合,card(D)>36,

... i ? 2003 (大于 n 时取模 n 的余数)列中 另一方面,将棋盘的第 i (i ? 1, 2,3,..., n) 行,第 i、i ? 1、、
的格子填入“*” 。将 1、2、3、…、2004n 填入有“*”的格子,其余的数填入没有“*”的格子。没有“*”

高一·联赛班·寒假第 7 讲·教师版

5

则 card(A∩B∩C∩D) = card(A∩B∩C)+card(D)-card(A∩B∩C∪ D)>12+36-48=0; 可以在集合 A∩B∩C∩D 中找一个同学 e,这 5 个同学 a,b,c,d,e 相互都认识. 5.

(1,3) (2,3) (1,4) (3,4) (1,5) (2,5) (3,5) (4,5) (1,6) 现在以 S 为顶点集作关联图,图中有 26 个孤立点

(4,12),(8,24),(12,36),(16,48) (10,15),(20,30),(30,45) (5,20),(10,40) (21,28) (6,30) (14,35) (24,40) (36,45) (7,42)

已知 T ? ?1,2,3,4,5,6,7,8? ,对于 A ? T , A ? ? ,定义 S ( A ) 为 A 中所有元素之和,问:

T 有多少个非空子集 A,使得 S ( A ) 为 3 的倍数,但不是 5 的倍数? 【解析】 对 于 空 集 ? , 定 义 S (? ) ? 0. 令 T0 ? {3, 6}, T1 ? {1, 4, 7}, T2 ? {2, 5, 8} . 对 于 A ? T , 令 A 0 ? A T 0, A ? 1 A T , 1A ? 2 A T ,则 2
S ( A) ? S ( A0 ) ? S ( A1 ) ? S ( A2 ) ? A1 ? A2 (mod 3) ,
因此, 3 S ( A) 当且仅当 A 1 ? A 2 (mod3) .有以下几种情况:

? A1 ? 0, ? ? ? A1 ? 0, ? ? A1 ? 3, ? ? A1 ? 3, ? ? A1 ? 1, ? ? A1 ? 2, ? ? ? ? ? ? ? ? A2 ? 0, ? ? A2 ? 3, ? ? A2 ? 0, ? ? A2 ? 3, ? ? A2 ? 1, ? ? A2 ? 2,
从而满足 3 S ( A) 的非空子集 A 的个数为
0 0 0 3 3 0 3 3 1 1 2 2 22 (C3 C3 ? C3 C3 ? C3 C3 ? C3 C3 ? C3 C3 ? C3 C3 ) ?1 =87.

{1,2,11,13,17,19,22,23,25,26,27,29,31,32,33.34,37,38,39,41,43,44,46,47,49,50},

14

35

7

42

21

28

若 3 S ( A) , 5 S ( A) ,则 15 S ( A) . 由于 S (T ) ? 36 ,故满足 3 S ( A) , 5 S ( A) 的 S ( A) 的可能值为 15,30.而 15=8+7=8+6+1=8+5+2=8+4+3=8+4+2+1 =7+6+2=7+5+3=7+5+2+1=7+4+3+1 =6+5+4=6+5+3+1=6+4+3+2 =5+4+3+2+1, 36-30=6=5+1=4+2=3+2+1. 故满足 3 S ( A) , 5 S ( A) , A ? ? 的 A 的个数为 17. 所以,所求的 A 的个数为 87-17=70. 注 本题为 07CWMO-1 6. 设 S={1, 2, ... , 50},求最小正整数 k,使 S 的任一 k 元子集中,都存在两个不同的数 a 和 b,满足 (a+b)整除 ab. 【解析】 设 a,b 的 最 大 公 因 数 为 d,a=a1d,b=b1d, 则 (a1,b1)=1. 代 入 (a+b)|(ab) 得 到 (a1+b1)|(a1b1d). 由 于 (a1+b1,a1)=(a1+b1,b1)=(a1,b1)=1,故(a+b)|(ab)的充要条件是(a1+b1)|d.令 d=k(a1+b1)得到满足条件的所 有数组 a=ka1(a1+b1), b= kb1(a1+b1).可设 a1<b1≤6,列出 S 中所有 23 个(a,b)对: (a1,b1) (1,2) (a,b) (3,6),(6,12),(9,18),(12,24),(15,30),(18,36),(21,42),(24,48)

5

20

30 15

45 6 3

36 12

18 4 8

9

10

40

24

48

16

其余 24 个点(23 条棱)分为 3 个连通支(见上图).从图看出,可以选取 38 个点互不相邻:26 个孤立点以及 12 个点{14,7,21,5,4,9,8,16,3,40,15,45}.因此 k≥39. 另一方面,任一 39 元子集中至少有 13 个点不是孤立点.它们分布在 12 个相邻对中: (14,35),(7,42),(21,28),(5,20),(9,18),(4,12),(8,24),(16,48), (3,6),(40,10),(15,30),(45,36), 必有一对的两数同属于子集,它们满足整除条件. 因此,k 的最小值是 39.

高一·联赛班·寒假第 7 讲·教师版

6

注 本题难度较大 7. 将 n 个白子与 n 个黑子任意地放在一个圆周上.从某个白子起,按顺时钟方向依次将白子标以 1, 2, , n .再从某个黑子起,按逆时钟方向依次将黑子标以 1, 2, , n . 证明:存在连续 n 个棋 子(不计黑白) , 它们的标号所成的集合为 ?1, 2,

, n? .

【解析】 取定标号相同的黑白棋子各一个,使得该对点所决定的劣弧中其他点(不含端点,

不计黑白)的个数最少.不妨假设该标号为 1. 在上述所取的开劣弧中, 只有一种颜色的棋子. 事实上,若两个 1 之间有两种颜色的棋子,则白 n 和黑 n 都在 其中,如图 1,于是两个标号为 n 的劣弧之间的点比两个标号为 1 的更少,矛盾! 如果开劣弧中全是白子, 有如下两种情形: (1) 开劣弧中的白子是 2,?,k,如图 2 所示, 则从标号为 1 的白子起,按逆时针方向连续 n 个棋子的标号所成的 集合为 ?1, 2,

n
1

n
1

, n? .

图1

(2)开劣弧中的白子是 k,k+1,?,n,如图 3 所示,则从标号为 1 的白 子起, 按顺时针方向连续 n 个棋子的标号所成的集合为

1

2

k
1

1

k

?1, 2,
n
1

n ,? .

图2
注 本题为 07CWMO-8

图3

如果开劣弧中全是黑子,或者开劣弧中没有棋子,类似可得.

高一·联赛班·寒假第 7 讲·教师版

7


数学竞赛讲义组合7-21

数学竞赛讲义组合7-21_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 数学竞赛讲义组合7-21_学科竞赛_高中教育_教育专区。第七讲 组合综合问题...

数学竞赛讲义:排列与组合

数学竞赛讲义:排列与组合【赛点直击】一、两个基本原理 加法原理 设 A 为完成...,7,有 21 个子集; 当 a∈[8],b∈[9]时,有 22 个子集. 故 A 的...

数学竞赛讲义组合1-6

数学竞赛讲义组合1-6_学科竞赛_高中教育_教育专区。...x2 ? x3 ? 21的非负整数解的个数,它等于 3 ...+x7=270 ① 在条件 7|xi (1≤i≤4)且 13|...

数学竞赛讲义组合计数

数学竞赛讲义组合计数_学科竞赛_高中教育_教育专区。...x2 ? x3 ? 21的非负整数解的个数,它等于 3 ...,将 M 中的元素按 ?7 7 7 7 ? 从大到小...

数学竞赛教案讲义(18)——组合

数学竞赛教案讲义(18)——组合 暂无评价|0人阅读|...7.赋值方法。 例 9 由 2×2 的方格纸去掉一个...(证明或否定) 2.21 个女孩和 21 个男孩参加一次...

高二数学竞赛班讲义 第六讲 组合问题

高二数学竞赛讲义 第六讲 组合问题_学科竞赛_高中教育_教育专区。高二数学竞赛...{ a1 , a2 ,…, a32 ,21} .若 1,3,7,42,63 中之一为集合 A 的...

柳铁一中组合高中数学竞赛同步讲义

高中数学竞赛同步讲义——组合数学基础 一、基础知识梳理 1、集合覆盖、分类、拆分 2、分类原理 3、容斥原理 4、加法原理 5、极端原理 6、抽屉原理 7、平均量...

数学竞赛教案讲义(13)——排列组合与概率

数学竞赛教案讲义(13)——排列组合与概率 隐藏>> 第十三章一、基础知识 排列组合...7.递推方法。 例 7 用 1,2,3 三个数字来构造 n 位数,但不允许有两个...

数学竞赛教案讲义(13)——排列组合与概率

数学竞赛教案讲义(13)——排列组合与概率 隐藏>> 第十三章一、基础知识 排列组合...7.递推方法。 例 7 用 1,2,3 三个数字来构造 n 位数,但不允许有两个...

高中数学竞赛讲义(十三)──排列组合与概率

高中数学竞赛讲义(十三) ──排列组合与概率 一、基础知识 1.加法原理:做一件...3.已知 A={0,1,2,3,4,5,6,7},映射 f:A→A 满足:(1)若 i≠j,...