答 案
见解析
解析
解：将每套试卷看作一个顶点，这些顶点构成集合
；
将每道题目也看作一个顶点，这些顶点的构成集合
．
若某套试卷
中包含某道题
，就在相应的顶点和之间连一条边，
这样得到一个二部图
．
设
中有个顶点，各顶点的度数分别为
，
，
，
．
因为每套试卷有道题，
所以，
中每个顶点的度数为．
故
．
又由于每两套试卷中至多只有一道题相同，
则对于
中任意两个顶点，
在
中至多有一个顶点对它们张有一个角，
即这种角的个数小于或等于
．
而在
中第个顶点处的角有
个，
于是，角的个数为
．
综上，
．
结合式
可将上式化简为
．
由常用不等式得
．
利用前述二部图，不难构造出
的例子(取
，
，
)．
所以，不同的题目至少有
道．
答 案
见解析
解析
模块
模块1：
1
1
例题1
X
Y
x ∈X
y ∈Y
x
y
X + Y
Y
n
x
1
x
2
⋯
x
n
4
X
4
x
+
1
x
+
2
⋯+ x
=
n
4 × 10 = 40
①
X
Y
C10
2
Y
i
C
x
i
2
C
+
x
1
2
C
+
x
2
2
⋯+ C
x
n
2
C
+
x
1
2
C
+
x
2
2
⋯+ C
⩽
x
n
2
C
10
2
①
x
+
1
2
x
+
2
2
⋯+ x
⩽
n
2
2C
+
10
2
40 = 130
x
+ x
+ ⋯+ x
⩽
(
1
2
n)2
n x
+ x
+ ⋯+ x
(
1
2
2
2
n
2)
⇒40 ⩽
2
130n ⇒n ⩾13
n = 13
x
=
1
x
=
2
4
x
=
3
x
=
4
⋯= x
=
12
3
x
=
13
2
13
例题2
证明：因为图中
中不含
，
所以，对于其中任意两个顶点，对它们所张的角的个数小于或等于．
另一方面，设图中各顶点的度数为
，
，
，
，则图中角的个数为
．
所以，
．
结合
，
得
．
同例，可得不等式
．
从而，即可得证．
答 案
见解析
解析
证明：因为
，
所以一个
阶完全图中含边
条．
因此题中图为
阶完全图中去掉边后所得，
把这边称为“去掉边”，
记
个顶点为
，
，
，
．
不妨设
为“去掉边”，
则把点
及其连边去掉，
于是余下的点图中至多有条“去掉边”．
不妨设
为一条“去掉边”，
把
及其连边去掉(如果已不含“去掉边”，则任去一点，下同)，
于是余下的阶图中至多有条“去掉边”．
不妨设
为一条“去掉边”，
把
及其连边去掉，
于是余下的阶图中至多有条“去掉边”．
不妨设
为一条“去掉边”，把
及其连边去掉，
于是余下的阶图中至多有条“去掉边”．
即此图为阶完全图或从阶完全图中去掉一边后所得的图，
不论如何必含有二部完全图
．
答 案
见解析
解析
证明：以这
个点为顶点，在取同一距离的两点间连一条边，得到一个图
．
因为到三个已知点距离相同的点至多只有一个，
所以，图
中不含
．
1
1
G
K
2,r+1
r
x1
x2
⋯
xn
C
+
x
1
2
C
+
x
2
2
⋯+ C
x
n
2
C
+
x
1
2
C
+
x
2
2
⋯+ C
⩽
x
n
2
rC
n
2
x
+
1
x
+
2
⋯+ x
=
n
2m
x
+
1
2
x
+
2
2
⋯+ x
=
n
2
rn n −1 +
(
)
2m
6
2m
⩽
(
)2
n rn n −1 + 2m
[
(
)
]
例题3
C
=
10
2
45
10
45
10
5
5
10
A1
A2
⋯
A10
A A
1
2
A1
9
4
A A
2
3
A2
8
3
A A
3
4
A3
7
2
A A
4
5
A
4
6
1
6
6
K
3,3
例题4
2012
G
G
K
2,3
由定理，图
的边数为
，
即
．
故不同距离的种数大于或等于
．
所以，不同距离的种数大于或等于
．
答 案
见解析
解析
证明：考虑二部图
，其中，
是由
的全体
元子集构成的，
是由
的全体元子集构成的．
若某个元子集
是由某个
元子集
去掉最小数得到的，
则
是图中的一条边．
可见，对于
，有
．
所以，
．
而对于
，当中的最小数为时，它恰好与
中的某个顶点相邻，
即顶点的度数
恰好等于中的最小数．
因此，所有最小数的和为
．
从而，其平均值为
．
答 案
见解析
解析
证明：考虑二部图
，其中，
．
而
是由所有
个排列构成的，
当且仅当
是某个排列
的不动点时，
是图中的一条边．
注意到，对于
，其恰好在
个排列中是不动点，
因此，
．
这样，
．
而对于
，若它的不动点有个，
则
．
依题意，在
中恰有
个度数为的顶点，
1
1
2
G
m ⩽
1 +
4
2012 (
4 × 2 × 2011 + 1)
m ⩽64304
64304
C
2012
2
32
例题5
X + Y
X
0, 1, ⋯, n
{
}
r + 1
Y
1, 2, ⋯, n
{
}
r
r
y ∈Y
r + 1
x ∈X
x, y
{
}
x ∈X
d x =
( )
1
d x =
x∈X
∑
( )
X =
∣
∣
C
n+1
r+1
y ∈Y
y
k
X
k
y
d y
( )
y
d y =
y∈Y
∑
( )
C
n+1
r+1
=
C
n
r
C
n+1
r+1
r + 1
n + 1
例题6
X + Y
X =
1, 2, ⋯, n
{
}
Y =
σ
, σ
, ⋯, σ
{
1
2
n!}
n!
i ∈X
σ
∈
j
Y
i, σ
{
j}
i ∈X
n −1 !
(
)
d i =
( )
n −1 !
(
)
d i =
i∈X
∑
( )
n!
σ
∈
j
Y
k
d σ
=
(
j)
k
Y
p
k
n ( )
k
故
中顶点的度数之和为
．
由引理即得
．
答 案
见解析
解析
解：先用反证法证明，
满足要求．
假设存在
个子集
，
，
，
，其中任意七个子集的并集元素个数大于或等于
，
但任意三个子集的交集为空集．
此时，令
，
则
构成一个二部图，
这里，
与
相邻当且仅当是
中的元素．
因为任意三个子集的交集为空集，
所以，
中每个元素至多出现在两个子集中，
即
中每个顶点的度数小于等于．
不妨设
中每个顶点的度数为(当某个顶点的度数为
时，
可以随意给它增加
个邻居)．
从而，图中的边数为
，
且图中恰有
个(顶点在
中的)角．
对于
中任意七个顶点，它们的邻居数大于或等于
，
则说明与这七个顶点有关的角至少有
个．
这样，对于剩下的八个顶点，对其中任意两个顶点所张的角的个数不超过
．
按下来，在
中固定
个顶点，其中共有
个“八点组”，每个八点组都至多张
个角，
而每个角会出现在
个八点组中，
所以，对这
个顶点所张的角的个数小于或等于
．
这表明，与
中剩下的那个顶点有关的角的个数大于，
即该顶点的度数大于或等于．
如此一来，
中任一顶点的度数大于或等于，
可知，图中边数大于或等于
．这与边数为
矛盾．
综上，
满足题设要求．
其次说明，当
时，存在
个子集
，
，
，
，
其中任意七个子集的并集元素个数大于或等于
，
但任意三个子集的交集为空集．
事实上，考虑这样的二部图
，
其中，
，且对于每个
，
，
在
中恰有一个顶点同时与
和
相邻(即对它们张一个角)．
容易验证，
中任意八个顶点至多张
个角，
从而，与剩下的七个顶点有关的角大于或等于
个，
即它们的邻居数大于或等于
．
综上，满足要求的最小正整数为
．
1
Y
d σ
=
σ
∈Y
j
∑
(
j)
kp
k
k=0
∑
n
n ( )
kp
k =
k=0
∑
n
n ( )
n!
例题7
n = 41
15
A1
A2
⋯
A15
41
Y =
A
, A
, ⋯, A
{
1
2
15}
X + Y
x ∈X
A
∈
j
Y
x
A
j
X
X
2
X
2
d < 2
2 −d
2 × 56 = 112
56
X
Y
41
41
56 −41 = 15
Y
14
C
14
8
15
C12
6
14
15 ×
<
C
12
6
C
14
8
49
Y
7
8
Y
8
8 × 15 = 120
112
n = 41
n = 40
15
A
1
A
2
⋯
A
15
40
X + Y
Y =
A
, A
, ⋯, A
{
1
2
15}
1 ⩽i ⩽7
8 ⩽j ⩽15
X
A
i
A
j
Y
x 8 −x ⩽
(
)
16
40
40
41
答 案
见解析
解析
证明：令
，
．
考虑完全二部图
．
当第行第列处填时，将边
染红；填时，则染蓝．
依题意，对于
中任意两个顶点
、
，
在
中至少可以找到
个顶点，
对它们所张的角的两边颜色不同．
把这种角称为“异色角”．
于是，图中异色角的个数大于或等于
．
特别地，当为奇数时，异色角的个数大于或等于
．．
另一方面，在
中任一顶点处，
设它引出条红色边，
条蓝色边，
则该顶点处异色角的个数
．
于是，图中异色角的总数小于或等于
．
综上，当为奇数时，
．
于是，为奇数时，命题得证．
当为偶数时，固定
中一个顶点，
设它引出
条红色边(相应的
个邻居构成集合
)，
引出
条蓝色边(相应的
个邻居构成集合
)．
又记
，
则
仍然满足题设要求，
也满足题设要求，
且
为奇数．
于是，利用已证的结果有
．
同理，
．
所以，
，
即为偶数时结论也成立．
答 案
见解析
解析
解：边数的最大值为
．
首先，如图所示，图中有个顶点和
条边，但其中没有四边形．
1
1
例题8
X =
1, 2, ⋯, m
{
}
Y =
1, 2, ⋯, n
{
}
X + Y
x
y
1
xy
0
X
x
1
x
2
Y
2
n
C
2
n
m
2
n
C
2
n + 1
m
2
Y
u
m −u
u m −u ⩽
(
)
4
m2
n
4
m2
n
C
⩽
2
n + 1
m
2
n ⋅
4
m2
⇒m ⩽n + 1 ⩽2n
n
n
Y
y
m1
m
1
X
1
m2
m
2
X
2
Y =
′
Y \ y
{ }
X
+
1
Y ′
X
+
2
Y ′
Y
=
∣
′∣
n −1
m
⩽
1
n −1 +
(
)
1 = n
m
⩽
2
n
m = m
+
1
m
⩽
2
2n
n
例题9
11
8
11
下面我们证明：若一个简单图有
条边，则其中一定含有四边形．
首先指出两个明显的事实：
设
是两个顶点．如果点
与点
，
，
均有边相连，
至少与
中的两点分别有边相连，
则图中必有四边形．
如果点之间连有条边，则图中必有四边形．
设有个顶点，
条边的图中没有四边形，其中点
是引出边最多的顶点之一．
设
共引出
条边，与
有边相连的顶点的集合为，
除点
及中的点之外的所有顶点的集合记为
．
于是由
和
知，中点之间连线数不超过
，
中点之间连线数至多为
，
与
之间连线数至多为
．
因而，图中连线总数至多为
．
当
时，边数小于
，矛盾．
点
恰引出条边：
．
设另外点是
，
，
．
于是
之间至多两条边，
之间至多条边，
这两个点集之间至多条边．
因为图中共有
条边，
故知类边数恰分别为，，．
不妨设第组的条线为
．
因为第组有两条边且二者没有公共端点，故
之间有一条边，不妨设为
，
于是
为四边形，矛盾．
点
恰引出条线，从而每点都引出条线．
设点
和
之间没有连线，两点各引出的条线分别为
，
．
于是由
知
与
至多有个公共点．
如果二者没有公共点，
则它们的各点间都至多有一条边，两个三点集之间至多有条连线．
从而图中连线总数至多为
，矛盾．
如果两个三点集之间恰有个公共点，
则考察第点
．由抽屉原理知，它引出的条线中必有两条引向同一个三点集，
这导致四边形，矛盾．
综上，我们证明了在有个顶点和
条边的图中必有四边形．从而，所求的边数的最大值为
．
答 案
见解析
解析
证明：本题条件中任意四点不共面实际是为了保证无三点共线，
故从图论角度看，
1
12
a
( )
A=B
/
A
C
1
⋯
C
k
B
C
, ⋯, C
{
1
k}
b
( )
4
5
8
12
A
1
( )
A
s ⩾5
A
S
A
S
T
a
( )
b
( )
S
[2
s ]
T
C
T
∣∣
2
S
T
T
∣∣
s +
+
[2
s ]
T +
∣∣
C
=
T
∣∣
2
7 +
+
[2
s ]
C
T
∣∣
2
s ⩾5
12
2
( )
A
4
AA
j = 1, 2, 3, 4
j (
)
3
B
1
B
2
B
3
A
, A
, A
, A
{
1
2
3
4}
B
, B , B
{
1
2
3}
3
3
12
3
2
3
3
3
3
A
B
j = 1, 2, 3
j
j (
)
1
A
, A
, A
{
1
2
3}
A
A
1
2
A A B
B
1
2
2
1
3
( )
A
3
3
A
B
3
AA
j
BB
j = 1, 2, 3
j (
)
a
( )
A
, A
, A
{
1
2
3}
B
, B
, B
{
1
2
3}
1
3
3
11
1
8
C
3
8
12
11
例题10
只需证明图中存在四边形即可．
解答本题可以援引例思路，
但直接应用不可行．
考虑将与
的点
相连的
个点去掉，剩下的点对有
个． 如例，没有
四边形时
．
同样
．
结合
不等式得
即
这与
及
矛盾．
所以图中必有四边形．
5
d v
⩾
( 1)
q + 2
v
1
d v
( 1)
Cn−d v
(
1)
2
5
C
⩾
n−d v
( )
2
C
i=2
∑
n
d v
−1
(
i)
2
d v
−1 =
i=2
∑
n
( ( i)
)
2l −n + 1 −d v
( )
Cauchy
2
n −d v
n −d v
−1
[
( 1)] [
( 1)
]
⩾
n −d v
−
n −d v
2
1 {
i=2
∑
n
[
( i)]2
i=2
∑
n
[
( i)]}
⩾
2l −n + 1 −d v
−2l −n + 1 −d v
2
1 { n −1
1
[
( 1)]2
[
( i)]}
n −1
n −d v
n −d v
−1
(
) [
( 1)] [
( 1)
]
⩾2l −n + 1 −d v
2l −2n + 2 −d v
[
( 1)] [
( 1)]
⩾q + q −d v
+ 2
q −q + 2 −d v
[ 3
2
( 1)
] [ 3
( 1)]
= nq −q + 2 −d v
nq −q −n + 3 −d v
[
( 1)] [
( 1)]
q + 1
n −d v
<
(
) [
( 1)]
nq −q + 2 −d v
( 1)
q n −d v
−1 ⩽
[
( 1)
]
nq −q −n + 3 −d v
( )
