组合数学--严文兰数学工作室

2023年12月9日发(作者：小学数学试卷题库免费下载)

2016年全国高中数学联赛8月份培训讲座

组合数学

严文兰数学工作室

1. 圆周上有n个点(n6)，每两点连一线段，假设其中任意三条线段在圆内不共点，于是任意三条两两相交的线段构成一个三角形，试求这些线段确定的三角形的个数。

2. 有n个人，已知他们任意2人至多通话一次，他们任意n2个人之间通话的总次数相等，都等于3k(kZ)，求n的所有可能值。

3. 设an为下述正整数N的个数：N的十进制表示中的各位数字之和为n，且每位数字只能取1,3或4，求证：a2n是完全平方数。

4. 给定n个不同实数，其所有全排列组成的集合为An，对于(a1,a2,,an)An，若恰有两个不同的整数i,j{1,2,,n1}，使得aiai1,ajaj1成立，则称该排列为“好排列”，求An中好排列的个数。

5. 投掷一次骰子，出现点数1,2,,6的概率均为

6. 试求所有的正整数n(n1)，使得存在正整数数列a1a2an，满足

1，连续掷10次，出现的点数之和是30的概率为？

61aiaj(1ijn)互不相同，且这些和分别被8除得到的余数中，每种余数各出现。

8

7. 设a1,a2,,an是1,2,,n的一个排列，求

Sn|a11||a22||ann|的最大值

8. 若0xi1(i1,2,,5)，则

M|x1x2|2|x2x3|2|x3x4|2|x4x5|2|x5x1|2的最大值是_________

9. 设实数x1,x2,,x2013满足如下两个条件：

(1)

1xi3(i1,2,,2013); (2)

x1x2x20136543

3222试求yx1x2x2013的最大值，并说明理由。

2016年全国高中数学联赛8月份培训讲座

10. 对于满足条件x1x2xn1的非负实数x1,x2,,xn，求S

11. 设p为给定的正整数，A是X{1,2,3,4,,2p}的子集，且具有性质：对任何xA，有2xA，求|A|的最大值。

12. 一个3×3×3的立方体由27个小立方体组成，将这27个小立方体每个都染成白色或者黑色，请设计一种方案，要求所染黑色的小立方体个数最少，使得这27个小立方体中每个小立方体所在的行与列与纵中都至少有一个黑色的小立方体。

13. 取集合{1,2,,n}的一批三元子集，其中每两个（取出的三元子集）至多有一个公共元素。记f(n)(xi1n4ixi5)的最大值。

n24n为这批三元子集的个数的最大值。证明

f(n)。

6

14. 在7×8的方格棋盘中，每个方格都放有一只棋。如果两只棋所在的方格有公共顶点，则称这两只棋是相连的。现在从这些棋中取出r只棋，使剩下的棋中没有5只棋在一条直线（横、竖、斜45°或135°方向）上依次相连，求r的最小值。

15. 设A是一个3×9的方格表，在每一个小方格内各填一个正整数，称A中的一个，若它的所有数的和为10的倍数。称A中的一个1mn(1m3,1n方格表为“好矩形”9)×1的小方格为“坏格”，若它不包含于任何一个“好矩形”。求A中“坏格”个数的最大值。

16. 有18支球队进行单循环赛，即每轮将18支球队分成9组，每组的2个队比赛一场，下一轮重新分组比赛，共赛17轮，使得每队都与另17支队各赛一场，按任意可行的程序比赛了n轮以后，总存在4支球队，他们之间总共只赛了1场，求n的最大可能值。

17. 求最大的正整数A，使1,2,,100的任何一个排列，都有10个连续的项的和不小于A。

18. 定义{x}为x的小数部分，即{x}x[x].现有n个在区间(0,1)中的实数1,2,,n，

证明必有一个实数，使得

19. 集合M{x1,x2,,x7}，它的子集A1,A2,,A7具有性质：

(i)M中的每一对元素同属于一个唯一的Aj(1j7)；(ii)3Aj7(1j7)。

证明：每两个子集Ai,Aj1ij7均有一个唯一的公共元素。

n{j}j1n1。

22016年全国高中数学联赛8月份培训讲座

20. 设Ai(i1,2,,30)是M{1,2,,1990}的子集，|Ai|660。求证：存在

i,j(1ij30)，使|AiAj|200。

21. 将边长为正整数m,n的矩形划分成若干边长均为正整数的正方形，每个正方形的边均平行于矩形的相应边，试求这些正方形边长之和的最小值。

22. 将凸多面体的每一条棱染成红色或黄色，两边异色的面角称为奇异面角，某顶点A处的奇异面角数称为该顶点的奇异度，记为SA。求证总存在两个顶点B和C，使得SBSC4。

23.

n,kN，S为平面上n个点的集合，对于S中任一点A，S中至少有k个点到A的距离相等。证明

k12n。

2

24. 6个点，每两个点之间有一条线相连，线染上红色或蓝色。证明一定有两个以这些点为顶点的三角形，每个三角形的边是同一种颜色（可能有公共的边）。

25. （1）把4×7棋盘上的每个小方格都染成白色或黑色。证明：在棋盘上必有一个矩形，它由棋盘的水平线和竖直线组成，矩形四角的四个小方格同色。

（2）给出4×6棋盘的一种黑、白染色方式，使得棋盘上不存在（1）中所说的矩形。

26. 12×12棋盘的144个小方格，用黄、红、白三种颜色染色，证明：存在一个以棋盘的水平线和竖直线组成的矩形，矩形四角的四个小方格同色。

27. 由n个点和这些点间的L条连线段组成一个空间图形，其中

nq2q1,L1q(q1)21(qN,q2)

2已知此图中任意四点不共面，每点至少有一条连线段，存在一点至少有q2条连线段，证明：图中必存在一个空间四边形（即由四点A、B、C、D和四条连线段AB、BC、CD、DA组成的图形）

28. 设M{1,2,,2005},A 是M的子集，若对任何ai,ajA,aiaj，都能以ai,aj为边长唯一地确定一个等腰三角形，求|A|的最大值。

*29. （第26届IMO备选题）设A是正整数集合N的子集，对任何x,yA,xy，有|xy|xy，25求|A|的最大值。

2016年全国高中数学联赛8月份培训讲座

30. 编号为1、2、„„、n的n本书排成一列（开始顺序是乱的），图书管理员想把它们按照正确的顺序排序（从左到右依次为1、2、3、„„、n）。每次他选一本位于它本该所处位置右边的书将它插入正确的位置。例如，若n=4，四本书依次为1、3、2、4时，管理员可以将编号为2的书放在第2个位置，这样四本书顺序变为1、2、3、4.求证：

(1) 无论如何选择操作顺序，只要操作不断地进行，肯定可以将所有的书排列成正确的顺序；

(2) 他最多可以操作多少步？

31. 把1993块正方形玻璃排成一行，每一块都涂上红、白、黄三种颜色之一。以下的操作称为一次调整：擦去两块不同色玻璃上的颜色，并把它们都涂上第三种颜色。求证：不论初始颜色的分布状况如何，总可以通过有限次适当的调整之后，使所有玻璃片都涂上同一种颜色，并且最后的颜色是唯一确定的，与具体的调整方案无关。

32. 从左到右编号为B1,,Bn的n个盒子共装有n个小球，每次可以选择一个盒子Bk，进行如下操作：若Bk在两端且至少1个小球，则可以向相邻盒子移1个小球；若Bk不在两端且至少2个小球，则可以向两边相邻盒子各移1个小球。求证：无论初始这些小球如何放置，总能经过有限次操作使得每个盒子中恰有1个小球。

33. 正五边形的每个顶点上写一个整数，使这五个整数之和为正。若有某三个相连顶点的整数依次为x,y,z，而中间的y0，则需要进行如下的操作：整数x,y,z分别换成xy,y,zy，只要所得的五个数中至少还有一个为负时，这种操作就继续进行。试问：这种操作是否在进行有限次后必定终止？

34. 对于整数n4，求出最小的整数f(n)，使得对于任何正整数m，集合{m,m1,,mn1}的任一个f(n)元子集中，均有至少3个两两互素的元素。

35. 设a1,a2,an(n4)是给定的正实数，a1a2an，对任意正实数r，满足

n2r(1ijn)的三元数组(i,j,k)的个数记为fn(r)，证明：fn(r)

4akaj

36. 设P0,P1,,Pn是平面上n+1个点，它们两两间的距离的最小值为d(d0)，求证：

ajaidn|P0P||PP||PP|()(n1)!

1020n3

2016年全国高中数学联赛8月份培训讲座

37. 在半径R=16的圆中有650个红点，证明存在一个内半径为2，外半径为3的圆环，其中至少有10个红点。

38. 如果F中任意两个元素Ai,Aj(1ijn)互不包含，那么F称为斯佩纳（r）族,间称S族。[n/2][n/2]求证S族的元素至多为Cn，即maxtCn。

练习

1. 如果一个集合不包含满足x+y=z的三个数x,y,z,则称之为单纯的，设M{1,2,,2n1}，A是M的单纯子集，求|A|的最大值。

2. 设整数n3，且a0a1a2an2n3都是正整数，证明：存在不同的整数i,j,k,l,m，使得

aiajakalam。

3. 设X{1,2,,100}，A是X的子集，若对A中任何的两个元素x,y(xy)，都有y3x，求|A|的最大值。（答案76）

4. 一个圆被432个点等分为432段弧，将其中108个点染成红色，108个点染成绿色，108个点染成蓝色，108个点染成黄色。求证：可以在每种颜色的点中各选3个点，使得由同色点构成的四个三角形都全等。

5. 给定正整数n，求最大的实数C，满足：若一组大于1的整数（可以有相同）的倒数和小于C，则一定可以将这一组数分成不超过n组，使得每一组数的倒数和都小于1.

6. 设正整数n3，如果在平面上有n个格点Pij|为有理数时，存在P1,P2,,Pn，满足：当|PPk，使得|PPk|均为无理数；当|PPij|为无理数时，存在Pk|均为有理数。ik|和|PjPk，使得|PPik|和|PjP那么称n是“好数”。

（1）求最小的“好数”； （2）问：2005是否为“好数”。

7. 设n,k为大于1的整数，n2，证明：存在2k个不被n整除的整数，若将它们任意分成两组，则总有一组有若干个数的和被n整除。

8. 设集合P{1,2,3,4,5}，对任意kP和正整数m，记f(m,k)5k[mi1k1]，其中[x]表示不i1大于x的最大整数，求证：对任意正整数n，存在kP和正整数m，使得f(m,k)n。

9. 给定正整数m,n，求具有下述性质的最小整数N(m)：若一个N元整数集含有模m的完全剩余系，则它有一个非空子集，其元素和被n整除。

10. 求满足下面条件的最小正整数k；对集合S{1,2,,2012}的任意一个k元子集A，都存在S中的三个互不相同的元素a,b,c，使得ab,bc,ca均在A中。