组合数学2019年7月真题及答案

2023年12月20日发(作者：11年奥迪a5敞篷跑车多少钱)

组合数学2019年7月真题及答案

1. （10分）3个0，2个1和3个7构成的8位数共有多少个？

答：

如果1作为首位，则7!/3!3! = 140

如果7作为首位，则7!/3!2!2! = 210

根据加法原则，共有140+210= 350个

2. （10分）某网红奶茶店有三种不同的奶茶。小王买了5杯奶茶，问共有多少种不同的奶茶组合？

答：有C(7，2)=21种不同的组合

3. （10分）设序列a1,a2,…a2019各项都是正整数，证明在这个序列中必存在若干个连续项组成的子序列，其各项之和为2019的倍数。

答：（同2019年1月真题）

序列a1,a2,…a2019中的任意数，除以2019的余数只可能是0，1，2，3，...2018

余数相加能被2019整除的数相加，一定能整除2019。

所以在此序列中，一定存在若干个连续项，使得每一项除以2019的余数之和为2019，即它们相加一定是2019的整数倍。

4. （10分）求满足递推关系hn=hn-1+9hn-2-9hn-3的hn的表达式，其中初始条件h1=0,h1=1,

h2=2.

答：

根据hn=hn-1+9hn-2-9hn-3得：特征方程为q^3=q^2+9q-9，解方程得：

q1=1, q2=3, q3=-3

则通解为hn=c1*(1)^n+c2*(3)^n+c3*(-3)^n

将初始条件h1=0,h1=1, h2=2代入得：从c1=-1/4, c2=1/3, c3=-1/12

所以通解为hn=-1/4+1/3*(3)^n-1/12*(-3)^n

5. （10分）证明组合恒等式

证明：（2019年国考真题）

C(n+m+1, k+1) = C(n+m, k+1) + C(n+m, k)

C(n+m, k+1) = C(n+m-1, k+1) + C(n+m-1, k)

C(n+n-1, k+1) = C(n+m-2, k+1) + C(n+m-2, k)

...

C(n, k+1) = C(n, k+1) + C(n, k)

依次代入整理即：

C(n+m+1, k+1) = C(n, k+1) + C(n, k) + C(n+1, k) + C(n+2, k) + ... + C(n+m, k)

6. （10分）求方程x1+x2+x3+x4=17整数解的个数，其中x1≥2，x2≥3，x3≥1，x4≥4.

答：

令y1=x1-2, y2=x2-3, y3=x3-1, y4=x4-4

则原方程可看作是方程y1+2+y2+3+y3+1+y4+4=17, y1, y2, y3, y4≥0的非负整数解的个数，即y1+y2+y3+y4=7，非负整数解的个数为C(4+7-1, 7)=120个

7. （10分）设图G是具有12个顶点的二部图。图G最多有多少条边？图G的顶点染色数是多少？

答：

图G最有36条边

顶点染色数是2

8. （10分）证明空间中不可能存在这样的多面体，它的面数是奇数，并且每个面由奇数条线段围成。

证明：（同2019年1月真题）

假设存在这样的多面体

由于每条边被两个面公用

所以每个面的边数和 = 多面体边数 * 2

由于它具有奇数个面，而且每一个面都有奇数条边，因此每个面的边数和是奇数*奇数也是奇数，这与多面体边数 * 2一定是偶数，矛盾

因此假设不成立，即不存在这样的多面体

9. （10分）图G有16个顶点，30条边，每个顶点的度只能是3、5、或6。已知图G有度为6的顶点2个，问度为3的顶点有多少个？度为5的顶点有多少个？

答：

设度为3的顶点有x个，度为5的顶点有y个

则x+y+2=16

6*2+3x+5y=30*2

解方程得：x=11, y= 3

即度为3的顶点有11个，度为5的顶点有3个

10. （10分）设Kn是n个顶点的完全图，用红蓝两种颜色给它的边任意染色。

1）证明当n=9时，图中必有蓝色的K4或红色的K3；

2）证明当n=14时，图中必定有蓝色的K5或红色的K3.

证明：（同2019年1月真题，2018年国考真题）

根据Ramsey定理，同时满足1），2）条件的最小的n=9，不妨这两题都取n=9，设9个顶点为v1,v2,v3,v4,v5,v6,v7,v8,v9

1）对9个顶点的完全图的边用红，蓝亮色任意着色，其结果必不可能使所有的顶点与之关联的边中都正好有3条边着红色或者蓝色。这是因为如若不然，既每个顶点正好三条边着红色，3*9=27，是奇数，是不可能的。因为每条红色的边都在两断点各计算一次，所得到的结果应该是偶数，这就证明了9个顶点中至少存在一个顶点，该顶点的8条边中着红色的边数

不是3.

2）假设顶点v9的8条边中，着红色的边数多于3，至少有4条，设这四条边为v1v9,

v2v9,v3v9,v4v9.只要在v1,v2,v3,v4中任意两点的连线着红色，设ViVj为红色边，则ViVjV9为红色边的三角形，其中i≠j，否则v1，v2,v3,v4是蓝色的边的完全四边形（见下图）

若v9的8条边中着红色的边数少于3条，最多不超过2条，则v9的蓝色边数至少有6条，设为v1v9,v2v9,v3v9,v4v9,v5v9,v6v9，由v1，v2,v3,v4,v5,v6,这6个顶点构成的完全图必有两个同色的三角形，若一个同色三角形是红色三角形，则满足问题的结论。如若是蓝色三角形，ViVjVk，则V9ViVjVk便是蓝色的完全四边形（见下图）