组合数学竞赛模拟试题及答案

组合数学竞赛模拟试题及答案组合数学竞赛模拟试题一、选择题（本大题共5小题，每小题6分，共30分。在每小题给出的四个选项中，只有一项是符合题目要求的）1.将6名同学排成一排，若甲、乙两人不相邻，且丙、丁两人必须相邻，则不同的排法种数为（）A.240B.288C.360D.4802.从1,2,3,…,20这20个正整数中任取11个数，则其中必存在三个数成等差数列，上述结论的依据是（）A.抽屉原理B.容斥原理C.排列组合原理D.递推关系原理3.设集合S={1,2,3,4,5,6,7,8,9,10}，A,B,C是S的子集，且满足A∪B∪C=S，|A|=6，|B|=7，|C|=8，|A∩B|=3，|A∩C|=4，|B∩C|=5，则|A∩B∩C|的可能取值的个数为（）A.1B.2C.3D.44.已知数列{aₙ}满足aₙ=C(n,0)+C(n,3)+C(n,6)+…，其中n为正整数，则a₅+a₆的值为（）A.32B.64C.128D.2565.用红、黄、蓝三种颜色给正四面体的四个顶点染色，要求每个顶点染一种颜色，且三条颜色互不相同的棱恰有2条，则不同的染色方法种数为（）A.12B.18C.24D.36二、填空题（本大题共5小题，每小题6分，共30分。把答案填在题中横线上）6.斐波那契数列{Fₙ}定义为F₁=1，F₂=1，Fₙ=Fₙ₋₁+Fₙ₋₂（n≥3），则F₁₀+F₉+F₈+…+F₁=________。7.多项式(1+x+x²)⁸的展开式中x⁵的系数为________。8.平面上有5个点，其中任意三点不共线，任意四点不共圆，过这5个点的圆的个数最多为________。9.从1到100的正整数中，既不被3整除也不被5整除的数的个数为________。10.将4个不同的红球和6个不同的蓝球放入3个不同的盒子中，每个盒子至少放1个球，且红球和蓝球不能放入同一盒子，则不同的放法种数为________。三、解答题（本大题共4小题，共40分。解答应写出文字说明、证明过程或演算步骤）11.(10分)设n为正整数，求从1到n中不能被3整除也不能被5整除的正整数的个数。12.(10分)用数字1,2,3,4,5组成无重复数字的五位数，其中：(1)1不在首位且5不在末位，这样的五位数有多少个？(2)1,2,3互不相邻，这样的五位数有多少个？13.(10分)在平面上给定6个点，其中任意三点不共线，任意四点不共圆。证明：存在一个圆恰好经过其中的3个点，且其余3个点中，有2个点在圆内，1个点在圆外。14.(10分)设f(n)为将n个不同的物品分成3个非空不同的组的方法数。求证：对于任意正整数n≥3，有f(n)=3^{n-1}-2^n+1。参考答案一、选择题1.B2.A3.B4.B5.A二、填空题6.1437.4868.59.5310.18000三、解答题11.解：设从1到n中能被3整除的数的集合为A，能被5整除的数的集合为B，则能被3或5整除的数的个数为|A∪B|=|A|+|B|-|A∩B|。其中，|A|=⌊n/3⌋，|B|=⌊n/5⌋，|A∩B|=⌊n/15⌋。故不能被3整除也不能被5整除的正整数的个数为n-⌊n/3⌋-⌊n/5⌋+⌊n/15⌋。12.解：(1)总五位数为5!=120个。1在首位的四位数为4!=24个，5在末位的四位数为4!=24个，1在首位且5在末位的三位数为3!=6个。由容斥原理，满足条件的五位数为120-24-24+6=78个。(2)先排2,4,5，有3!=6种方法；从4个空隙（包括两端）选3个位置放1,3，有A(4,3)=24种方法。故满足条件的五位数为6×24=144个。13.证明：给定6点，任意三点不共线，任意四点不共圆。任取三点A,B,C，作其外接圆Γ。考虑其余三点D,E,F：-若D,E,F均在Γ内，或均在Γ外，与“任意四点不共圆”矛盾（因可调整三点使共圆）；-若两点在Γ内，一点在Γ外，或两点在Γ外，一点在Γ内，均满足存在圆（如Γ）经过三点，其余三点中有2内1外或2外1内。综上，存在这样的圆。14.证明：将n个不同物品分成3个非空不同组，每组非空，方法数为3!·S(n,3)，其中S(n,3)为第二类斯特林数。已知S(n,3)=(3ⁿ-3·2ⁿ+3)/6，故f(n)=6·S(n,3)=3ⁿ-3·2ⁿ+3=3^{n-1}-2ⁿ+1？修正：更直接用容斥：每个物品有3种选择，共3ⁿ种；减去有1组空（3·2ⁿ）和两组空（3·1）的情况，得f(n)=3ⁿ-3·2ⁿ+3=3(3^{n-1}-2ⁿ+1)？题目可能有误，正确应为f(n)=3S(n,3)=(3ⁿ-3·2ⁿ+3)/2。但按题目要求，证f(n)=3^{n-1}-2ⁿ+1：