当前位置:首页 >> 学科竞赛 >>

组合题选讲-大字稿(1) (1)


周敏泽

2014 年 8 月

组合题选讲 试题选讲: 1.已知一凸 n 边形的任意相邻两个内角的差都是 20°. 试求 n 的最大值.(2014 年江苏) 分析——求最值,两个方面的叙述;

n 越大,内角越大,不能无限大,凸边形的内角小于 180;
从最大内角开始,转一圈,减多少,得增多少; 能估计最值的

大小; 怎么构造?

解:(1)证明 n≤34. 记凸 n 边形为 A1A2?An,则 A2=A1±20 ,
°

A3=A2±20°=A1±20°±20°,?,(“±”为“+”和“-”中的一个)

n 个项相加
° ° ° ° ° °

n 个项相加

An+1=A1±20 ±20 ±?±20 = A1,即±20 ±20 ±?±20 =0°,
则“+”号的个数与“-”的个数相等,所以 n 为偶数. 设最大的内角度数是 x,则其相邻内角的度数是 x-20°, 由题意,任意相邻两角的度数不相同,且其和不超过 2x-20°, 平均不超过 x-10°, 故 A1+A2+?+An=(n-2)?180° ≤ n(x-10°), 所以 nx≥(n-2)?180°+n?10°. 因为 x<180°,所以 n?180°>nx≥(n-2)?180°+n?10°, 从而 n<36,又因为 n 为偶数,所以 n≤34.——上确界

(2)证明 n=34 能取到. 不妨设凸 34 边形内角中度数只有两个值 x 和 x-20°,相间出现, 如图构造,圆 O 的内接正 34 边形 A1B2A3B4?A33B34 中, 延长 OBk 到 Ak 使得∠BkAk+1Ak=5°, Ak-1 Bk 1 O Bk+2 Ak+1

k=2,4,?,34;

Ak

Ak+2

周敏泽

2014 年 8 月

则 x-20°=∠A2i-1A2iA2i+1 = 180°?32 -2?5°>0°, 34 180°?32 +2?5° 34 180°?32+340° <180°, 34

x=∠A2iA2i+1A2i+2=

=

凸 34 边形 A1A2A3A4?A33A34 满足条件. 由(1)(2)可知,n 的最大值为 34.

2.设 S={1,2,3,?,11},对 S 中的每一个 7 元素子集,将其中的 7 个数从小到大排列,取出中间的数, 则所有取出的中间数的和等于 分析——哪些数会出现在中间? 这些数出现几次? 解:任一个 7 元素子集按大小排列,中间的数大于等于 4 小于等于 8; 3 中间数为 4 时,子集合的个数有 C3 3C7; 3 中间数为 5 时,子集合的个数有 C3 4C6; 3 中间数为 6 时,子集合的个数有 C3 5C5; 3 中间数为 7 时,子集合的个数有 C3 6C4; 3 中间数为 8 时,子集合的个数有 C3 7C3; 所有中间数的和为 3 3 3 3 3 3 3 3 3 4?C3 3C7+5?C4C6+6?C5C5+7?C6C4+8?C7C3 =12?(35+80)+6?100=12?(35+80)+6?100 =6?330=1980 .(2014 年上海)

3.将一个正 2014 边形的每一条对角线染上 n 种颜色中的一种,使得对于任何两条在多边形内部有交点的 对角线,他们的颜色不同.求 n 能取得的最小可能值.(2014 年英国) 分析:可以先研究正六边形或正 12 边形.

2

周敏泽

2014 年 8 月

A1007+i A1006+i Ay

A1 A2 Ax Ai-1

解:设正 2014 边形 A1A2?A2014 的外接圆为圆 O, 对角线中有 1007 条是圆 O 的直径,均交于圆心 O.

Az

Ai

若 n 种颜色染色后使得对于任何两条在多边形内部有交点的对角线颜色不同, 则此 1007 条直径不同色. 所以

n≥1007.

与直径 AiA1007+i 平行的对角线 Ai+kA1007+i-k 可染同种颜色, 对角线 Ai+k-1A1007+i-k 介于两条平行的对角线 Ai+k-1A1008+i-k、Ai+kA1007+i-k 之间,可染同色. 其中 k=0,±1,±2,?,±502.

i=1,2,?,1007.
所有对角线按一侧正 2014 边形的顶点数的奇偶分为两大类, 按方向可分为 2014 类, 对给定的 i,一种颜色染遍相邻两个方向上所有对角线,

i 的值不同,对应的两个方向的对角线不重叠,
故以上方案给对角线染色遍及了所有对角线. 故 1007 种颜色可按要求染色. 综上,n 的最小值为 1007.

4. 对平面上的每个点染红色或蓝色. 证明: 存在同色的三个点构成的三角形, 其三边长分别为 1, 2, 3. (2013 年泰国) 析:三边长 1,2, 3,构成特殊直角三角形, 正三角形的一半. G B C B A 以 2 为边作正三角形, 三个顶点中的两个必同色;设 A,D 同 A 3 D F D

O

E

周敏泽

2014 年 8 月

色; 以 AD 为直径作圆,A,B,C,D,E,F 六等分圆, 若 B 或 C 或 E 与 A 同色,则△ABD 或△ACD 或△ADE 即为所求; 否则△BCE 为所求.

——1995 年全国联赛:平面上每个点染红、蓝两色之一. 证明:存在两个相似三角形,相似比为 1995,每个三角形三个顶点同色.

5.8 个人参加一次聚会. (1)如果其中任何 5 个人中都有 3 个人两两认识,求证:可以从中找出 4 个人两两认识; (2)试问:如果其中任何 6 个人中都有 3 个人两两认识,那么是否一定可以找出 4 个人两两认识?(2006 年 女子数学奥林匹克) 分析:(1)从何处入手?极端、反面; (2)结论是肯定还是否定?特殊构造. 解:(1)分类讨论:设 8 个人 A1,A2,A3,A4,A5,A6,A7,A8. ①若 8 个人中存在 3 人两两互不认识,如 A1,A2,A3 互不认识. 则 A1,A2,A3,Ai,Aj 中有三人两两认识, 只能是 Ak,Ai,Aj 三人,k 为 1 或 2 或 3,

Ai,Aj 两人认识,i,j=4,5,6,7,8,存在五人两两认识;
即有四人两两认识. ②当 8 个人中任意 3 人都不是两两互不认识, 即 8 人中任意三人中总有两人认识. 若 8 人中有人最多只认识 3 人,另有 4 人不认识, 设 A1 认识 A2,A3,A4,不认识 A5,A6,A7,A8. 则当 i,j=5,6,7,8 时,A1,Ai,Aj 三人必中有两人认识,

Ai,Aj 两人认识,
故 A5,A6,A7,A8 四人两两认识; 4

周敏泽

2014 年 8 月

③当 8 人中任意三人中总有两人认识. 若 8 人中有人最少认识 5 人,设 A1 认识 A2,A3,A4,A5,A6, 则 A2,A3,A4,A5,A6 五个人中有 3 个人两两认识, 加上 A1 四人两两认识; ④当 8 人中任意三人中总有两人认识. 若 8 人中每个人都只认识 4 人, 设 A1 认识 A2,A3,A4,A5,不认识 A6,A7,A8. 若 A2,A3,A4,A5 两两认识,即为所求; 否则,存在两人不认识,设 A2,A3 不认识, 由 A1 不认识 A6,A7,A8, 则 A6,A7,A8 两两认识, 若 A2,A3 两人中有人与 A6,A7,A8 都认识, 则此人与 A6,A7,A8 构成四人组,两两认识; 否则,A2,A3 都至少不认识 A6,A7,A8 中的一个人, 且不是同一人(否则三人两两不认识), 设 A2 不认识故 A6, A3 不认识故 A7, 则 A1,A2,A3,A6,A7 五人的关系图如上,其中任意三人都不是两两认识,与题设矛盾. 此情况不可能出现; 综上,8 人中总存在四人,他们两两都认识. (2)试问:如果其中任何 6 个人中都有 3 个人两两认识,那么是否一定可以找出 4 个人两两认识?(2006 年 女子数学奥林匹克) 分析:结论是肯定还是否定?特殊构造. ——读图,三个连续的点连实线表示两两都认识;四个点 解:(2)如图,圆周上 8 个点表示 8 个人, 用实线段表示端点两人认识. 图中相邻的三个点构成实线三角形,即相应的三人两两认识. 则 8 个点任意去掉 2 个点,总有一段弧上有三个点相邻, 即任意六人中必有三人两两认识. 而任意四点,总有两点连线一侧含有 8 点中的 3 点或 4 点,连线非实线.?? 5 A6 A5 A4 A8 A7

A1 A7 A6

A3

A2

A1
A2 A3

周敏泽

2014 年 8 月

6.设平面点集 P={ P1,P2,?,P2014},P 中任意 3 点不共线,将 P 中所有点任意分成 83 组,使每组至少 3 个点且每点恰属于一组,然后将同一组的任意两点用线段相连,不同组的任意两点不连线段,这样得到 一个图案 G.不同分组得到不同的图案,将图案中以 P 中点为顶点的三角形个数记为 m(G). (1)求 m(G)的最小值 m0; (2)设 G 是使 m(G )= m0 的一个图案,若将 G 中的线段(指以 P 中点为端点的线段)用四种颜色染色,每条 线段恰染一色. 证明:存在一种染色方案,使 G 染色后,不存在以 P 中点为顶点的三边颜色相同的三角形.(全国联赛) 分析: (1)多元函数取最值,不是均匀就是极端. 从简单的开始,??. 解:(1)设给定 n 个点分两组,分别属于两组的点不连线, 同一组的任意两点连线,构成的三角形个数为 g. 设一组有 t 个点,则另一组 n-t 个点,构成三角形个数 g, 3 6g=6C3 t+6Cn-t=t(t-1)(t-2)+(n-t)(n-t-1)(n-t-2) =t -3t +2t+(n-t) -3(n-t) +2(n-t) = t -3t +2t+n -3n t+3nt -t -3n +6nt-3t +2n-2t =3(n-2)[t -nt]+ n -3n +2n. 当常数 n 是偶数,t= 时,g 取最小值, 2 当 n 是奇数,t=
2 3 2 3 2 3 2 2 3 2 2 3 2 3 2

*

*

*

*

n

n±1
2

时,g 取最小值.

即两组的点的个数之差为 0 或 1 (不能均分)时,三角形个数最少. 对于 2014 个点分 83 组,当存在两组点的个数之差大于 1 时,调整均衡此两组点的个数,m(G)会变小, 故此时 m(G)不是最小值. 所以,当任意两组点的个数之差不大于 1 时,m(G)最小. 因为 2014=24?83+22,则 22 组取 25 个点,61 组取 24 个点可使得 m(G)取最小值 m0. 3 其中 m0=22 C3 25+61C24=174064. 6

周敏泽
*

2014 年 8 月

(2) G 中点分为 83 组,61 组有 24 个点,22 组有 25 个点, 注意如下染色方案:设组 X 中恰有 25 个点, 把组 X 平均分为 5 个小组 Yi={Ai,Bi,Ci,Di,Ei},i=1,2,3,4,5. 每个小组中的点连线染色按下图(1)分别用第 1 第 2 两种颜色染色,小组与小组之间的两个点连线染色 按下图(2)分别用第 3 第 4 两种颜色染色,

则三点在同一小组, 三角形三边不 会同色; 两点在一小组, 第三点在另一小组 的三角形三边不会同色; 三点分别在三个小组的三角形三 边也不会同色。

Ai Ei ② Di ① Ci Y4 Bi Y5

Y1 Y2 ④ ③

Y3

当组 X'中只有 24 个点,可以先虚拟加一个点,按上述方法染色后,擦去该点及由此点连出的线段。 得到的染色结果也符合要求。

7.将每一个整数染成红色或蓝色.已知对于任意一个有限的连续整数集 A,红色整数个数与蓝色整数个数 之差的绝对值不大于 1000.证明:存在一个满足上述条件且由 2000 个连续整数组成的集合 A,使得红 色整数和蓝色整数各 1000 个.(意大利 2013) 分析:——每一个整数都染色了,且对于任意有限的连续整数集 A,红色整数个数与蓝色整数个数之差的 绝对值不大于 1000. 数集{1,2,3,?,2000}中红色的数 r1 个,蓝色的数 b1 个, |r1-b1|≤1000,我们关心 b1=1000?r1=1000? 数集{2,3,?,2000,2001}中红色的数 r2 个,蓝色的数 b2 个, |r2-b2|≤1000;我们关心 b2=1000?r2=1000? 数集{3,4,?,2001,2002}中红色的数 r3 个,蓝色的数 b3 个, |r3-b3|≤1000;我们关心 b3=1000?r3=1000??? 数集{k,k+1,k+2,k+3,?,k+1999}中红色的数 rk 个,蓝色的数 bk 个,|rk-bk|≤1000;证明存在

bk=1000!rk=1000!
7

周敏泽

2014 年 8 月

——单独看一个数集,不能看到方向,但整体地看,会有所发现:

解:设数集{k,k+1,k+2,k+3,?,k+1999}中红色的数恰有 rk 个, 若 r1=1000,则数集{1,2,3,?,2000}即为所求; 若 r1<1000,则 r1≤999,假定 rk≤999,k=1,2,?,1000001, 则 r1+ r2001+ r4001+??+ r1000001≤999?501, 在数集{1,2,3,?,1002000}中,蓝色的数与红色的数之差

d≥1002000-2?999?501=1002,与题设矛盾.
即当 k=2,3,?,1000001 时,存在 rk≥1000. 设 rj+1 是 r1,r2,?,r1000001 中从左到右第一个不小于 1000 的红色数个数,即 rj≤999,rj+1≥1000, 注意到 rj 是数集{j,j+1,j+2,j+3,?,j+1999}中红色的数的个数,

rj+1 是数集{j+1,j+2,j+3,?,j+1999,j+2000}中红色的数的个数,
若 j,j+2000 同色,rj= rj+1,不合; 若 j 红,j+2000 蓝,rj+1= rj-1,不合; 惟有当 j 蓝,j+2000 红,rj+1= rj+1 可能,此时 rj=999,rj+1=1000, 即数集{j+1,j+2,j+3,?,j+1999,j+2000}中红色数的个数与蓝色数的个数均为 1000.

7-1.S 是由在同一条直线上 6n 个点构成的一个集合,随机地选择其中的 4n 个点染成蓝色,其余 2n 个染 成绿色.证明:存在一条线段,使其包含 S 中的 3n 个点,其中 2n 个点位蓝色,n 个点为绿色.(2008 年巴西)

8.将一个边长为 n 的等边三角形细胞平均分成 n 个小等边三角形的小细胞,其中一些细胞是被感染的, 一个没有被感染的细胞当且仅当其相邻细胞至少有两个被感染时,它被感染.当 n=12 时,所有细胞均 被感染了.求在初始时细胞中被感染小细胞数目的最小值. (捷克-斯洛伐克 2013) 分析:这是组合最值问题; 8

2

周敏泽

2014 年 8 月

初始时,角上的小细胞必定被感染; 感染的交界处几种情况? 感染一个细胞,感染的边界长度会减少 1 或 3 单位; 全部被感染时,感染区域的边界为 3n. 解:假定初始时有 k 个细胞被感染,n -k 个细胞尚未被感染,若干时间后,全部被感染。反向考查被感 染区域的边界, 3n+(n -k)≤3k,即 4k≥n +3n, 当 n=12 时,4k≥12 +36,即 k≥45. 构造如图初始状况,证明可感染全部.
2 2 2 2

思考题: 2.在桌上有 100 张标有 1~100 的正整数的卡片.安德烈和尼克按照如下方式轮流取卡片:若安德烈取标 号为 n 的卡片,则尼克就要取标号为 2n+2 的卡片.问:这两个人一共最多可以取到多少张卡片? 分析: 1.将 1,2,?,12 排为一个数列,其排法数为 12! ,排列需使数列中恰有一项比前一项小.求在 12!个数 列中满足条件的个数.(荷兰 2012) 3.30 名女生围着新年松树跳圈舞,其中,13 名女生穿红色连衣裙,17 名女生穿蓝色连衣裙.跳舞结束后, 询问每名女生同样一个问题:你的右邻是否穿蓝色连衣裙?最终,只有那些两侧相邻且连衣裙颜色相同 的女生回答对了.试问:可能有多少名女生给予肯定的回答(意即回答“是”)? 4. n 名女生与 4 名男生参加舞会, 成对跳舞, 每对中有一名男生和一名女生, 且他们有可能会更换舞伴. 求 最小的 n,使得舞会结束时,要么有两名男生和两名女生按他们间的每种组合均跳过,要么有两名男生 和两名女生两两均没有跳过.(匈牙利 2013 决赛)

9 3 1 2

周敏泽

2014 年 8 月

5.在 n?n 的方格表每列的上面标注 1,2,?,n.在方格表的每个方格中 数,需满足:方格表中每行均按某一顺序含有 1,2,?,n,每列也按同 含有 1,2,?,n,对于每个方格.若此格中所填数字大于该格所在列的 就将该格染为黑色.图为 n=3 时的例子. (1)当 n=5 时,能否通过这种染色,使得每行的黑格数相同? (2)当 n=10 时,能否通过这种染色,使得每行的黑格数相同?

1 2

2 3

3 1

写一个 一顺序 列数,

6.为了举办一场赛事,要组成若干委员会,其中,每个委员会均为 5 个人的子集,且满足:(1)每个委员 会至少有一名成员;(2)没有两个委员会组成相同;(3)任两个委员会至少有一名共同成员. 假设 14 个委员会已经形成,证明:还能再形成一个委员会.

10


相关文章:
组合题选讲-大字稿(1) (1)
组合题选讲-大字稿(1) (1)_学科竞赛_高中教育_教育专区。2014年全国高中数学联赛江苏冲刺辅导(扬州大学,8.10-16) 讲解人:周敏泽周敏泽...
组合题选讲
周敏泽 2014 年 8 月 组合题选讲试题选讲: 1.已知一凸 n 边形的任意相邻两个内角的差都是 20° . 试求 n 的最大值.(2014 年江苏) 分析——求最值,...
排列组合题目精选(附答案) (1)
排列组合题目精选(附答案) (1)_高三数学_数学_...10、某高校从某系的 10 名优秀毕业生中选 4 人...排列组合精选60题 及详解... 19页 1下载券 历年...
竞赛题选讲(一)
年 级 六年级 刘大占 学 科 奥数 版 本 内容标题 编稿老师 竞赛题选讲(一) 【本讲教育信息】一. 教学内容: 竞赛题选讲(一) (一)思路指导 例 1. 把...
第1讲:几何证明题选讲(一)
1讲:几何证明题选讲(一)_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档第1讲:几何证明题选讲(一)_数学_高中教育_教育专区。几何证明选讲(...
13综合题选讲(1)新
第十三讲 综合题选讲(1) 【典型例题 1】 (1)探究新知:如图 1,已知△ABC...()...(A) (4,0) (C) (—2 2 ,0) 解析:B (B) (1,0) (D) (...
初三综合题选讲(一)
初三综合题选讲(一)_数学_初中教育_教育专区。综合题选讲(一) 、选择、填空类 1.如图,在平面直角坐标系中,个圆与两坐标轴分别交于 A、B、C、D 四点...
竞赛题选讲(一)同步练习
竞赛题选讲(一)同步练习_学科竞赛_小学教育_教育专区。六年级奥数通用版竞赛题选讲(一)同步练习 [答题时间:30 分钟](二)尝试体验 1. 一根竹笋从发芽到长大,...
思易学教育小六数学竞赛题选讲(一)
王老师 学科 奥数 版本 内容标题 编稿老师 竞赛题选讲(一) 【本讲教育信息...(假设排水管流速不变) 3 B C (1)同时打开 AB 两水槽排水管 10 分钟,这时...
更多相关标签:
组合问题说课稿 | 中国传统文化专题选讲 | 不等式选讲高考题 | 不等式选讲高考真题 | 经济管理专题选讲 | 几何证明选讲高考题 | 整数问题选讲 | 不等式选讲解题技巧 |