文档文本内容
答 案
见解析
解析
解：当
时，安娜获胜．
当
时，安娜只能从中取走一个，剩下的一个伯塔取走，则伯塔获胜．
用数学归纳法证明：当
时，伯塔可获胜．
当
时，
，结论成立．
假设
时，伯塔可获胜．当
时，
．
设第一次安娜取球数为．若为奇数，则剩下的球数也为奇数，伯塔全部取走即可获胜．若为偶
数，则
．按照规则，伯塔可以取到
个球，两次取球之后，给安娜剩下
个球．由归纳假设，伯塔可以获胜，上述命题得证．
若
为奇数，则安娜第一次全取即可获胜．
若
为偶数，且
不为
型，则必存在某个
满足
．
于是，
．
安娜第一次取
个球，剩下
个球给伯塔．由
，知安娜可获胜．
综上，当且仅当
时，伯塔有获胜策略，即
当
时，
．
答 案
见解析
解析
解：露丝有必胜策略．
考虑
(奇数
)的方格表．在某一时刻，行或列所标记的格有、、个，则称对应的行
或列是空的、不完全的、满的．
露丝可进行两步操作．
【第一步】阿德第一次标记有如下性质：
对于空行
或空列
，在标记完后仍有空行，则称这样的标记为“标准的”．露丝的标准标记是在阿
德标记后，选择一个不同于空行
的行
，标记行
与列
的交叉格，称这种规则为“标准方案”，
且使列
为满的．于是，列
不能再被标记．若阿德做出了标准标记，则露丝就给出标准方案．显
模块
模块1：
1
1
例题1
N = 1
N = 2
1
( )
N = 2 −
a
2 a ⩾2, a ∈Z
(
)
a = 2
N = 2
a = k −1 k ⩾3
(
)
a = k
N = 2 −
k
2
x
x
x
x ∈2, 2
−2
[
k−1
]
2
−
k−1
x
2
−
k−1
x
2
( )
N
3
( )
N
N
2 −
a
2
k ⩾3
2
−
k−1
2 < N < 2 −
k
2
N −2
−2 ⩽
( k−1
)
2
N
N −2
−2
( k−1
)
2
−
k−1
2
1
( )
N = 2 −
a
2 a ⩾2, a ∈Z
(
)
N = 2 −
a
2 ⩾100000
N
=
min
2
−
17
2 = 131070
例题2
n × n
n ⩾3
0
1
2
R
C
R
R′
R′
C
C
C
然，对于每列，在露丝给出标准方案后，列要么是空的要么是满的．从而，阿德下次标记是在空行
中进行．对于每一个标准标记对应着一个标准方案，因此，只要阿德按照标准标记露丝就不会输．
假设阿德采用非标准标记．则令
为第一个非标准标记，
在空列
中，其有两种可能：
在不完全的行
中；
在最后剩下的空行中．
因为是奇数，所以，两次标记后仍留有奇数个空行．
于是，对于
，方格表中仍有空行．从而，露丝标准方案是仍取不同于空行
的行
，标记行
与列
的交叉格．对于
，在标记完
后，所有的行均为不完全的，露丝选择不同于行
的行
，标记行
与列
的交叉格，则行
是满的．露丝可以按照第一步标记．于是，所得到的表格满
足：
(i)空行的行数
为偶数；
(ii)不完全行的个数为偶数；
(iii)不存在不完全的列．
在标记
之前，
为奇数，为偶数，在情况
、
变化后，
减少而不变于是，性质(i)、(ii)
成立注意到，只要露丝进行标记后，(iii)显然成立．
【第二步】露丝只要保证自己每次标记满足性质(i)
(iii)即可．令阿德在空行
与列
的交叉格标记
．因为在标记
后不存在不完全的列且为满的，所以，在标记
前列
也是空的故标记
后行
与列
均是不完全的．
由性质(i)，知在标记
后
为奇数．从而，露丝可以选择不同于行
的空行
和列
的交叉格进行
标记．则标记方案是使列
为满的，行
为不完全的．于是，在阿德和露丝标记后，
减少，增
加，在露丝给出方案后，性质(i)
(ii)仍不变．类似地，阿德在不完全行
与列
的交叉格标记
由于在标记前列
为空的，则标记
使行
为满的，列
为不完全的．
故由性质(ii)，知在标记
后，为奇数．于是，露丝可以选择不同于行
的不完全行
和列
的交
叉格进行标记．从而，标记方案是使列
为满的，行
为满的．因此，在阿德和露丝标记后，增
加，
不变，在露丝给出方案后，性质(i)
(ii)仍不变．
因为游戏是有限的，只会存在一个输者，所以，露丝可在阿德标记后，按照第二步给出的标记方案
就不会输．
综上，露丝获胜．
答 案
见解析
解析
解：当
时，乙必胜．
考虑两个相邻染色点之间的弧．若弧的两个端点均为白色(或黑色)，则称此弧为白弧(或黑弧)；否
则，称此弧为灰弧．在游戏的最后，所有的白弧上的点均为白色；黑弧上的点均为黑色；灰弧上的
点一半为白色、一半为黑色，其弧中点为无色的．
设
、分别表示标记的白点、黑点的个数，
、
分别表示白弧、黑弧的个数，
表示灰弧的个
数．则
且
，即
．①
为了方便起见，不妨设此圆的周长为．
下面给出乙的必胜策略．
当甲画点之后，乙先考虑以甲画的点为圆内接正边形顶点的图形，然后乙选择这个正边形的
其他顶点，直到不能这样选择为止
当正边形的所有顶点均已经染色，乙开始选择最长的白弧(之一)，在这段弧上任意地选择一个
点染成黑色．因为乙染色之前的点数总比甲少一个，所以，由式①，知白弧至少有一个．
1
M
M
C
1 M
( )
R
2 M
( )
n
1
( )
R
R′
R′
C
2
( )
M
R
R′
R′
C
R′
E
t
M
E
t
1
( )
2
( )
E
1
t
∼
R
C
M
M
M
C
M
R
C
M
E
R
R′
C
C
R′
E
2
t
2
∼
R
C
M
C
M
R
C
M
t
R
R′
C
C
R′
t
2
E
∼
例题3
n ⩾2
w
b
W
B
G
2W + G = 2w
2B + G = 2b
W −B = w −b
1
1
( )
n
n
2
( )
n
因此，这样的步骤总可以实现
在甲最后一步时，有下面的几个基本关系：
(i)若有黑弧，则其长度为
．这是因为乙除了在正边形顶点处画的点之外，均是在两个白点之间
画点(不同于正边形的顶点)．从而，乙画的点不会相邻，这样的点不会是黑弧的端点；
(ii)因为此时标记的点的总数为
，弧的总数为
，所以，至少一段弧以正边形相邻的两个
顶点为端点，且这段弧中不包含标记的点，将这种弧称为“空弧”．
(iii)任意一段白弧的长度小于
．
事实上，设甲染了边形的个顶点．在
之后，每段弧的长度均不大于
，且等于的情况只是在
弧的两端为正边形相邻的两个顶点．
在
中，乙进行了次操作，每一次均在最长的弧中画点，于是，乙会在每一个长度为
的白弧中
画点，直到每一段白弧的长度均小于
．
因此，空弧一定是黑弧或灰弧．若其中至少有一段黑弧，则由式①知至少两段白弧．从而，乙在最
后一次画点时，在白弧中画点．此时，黑弧与白弧的条数一致，但白弧的长度小于
，而黑弧的长
度为
．因此，乙获胜．若所有的空弧均为灰弧，则没有黑弧，再由式①，知此时恰有一段白弧，
且这段白弧的长度
．在
中，乙在灰弧上面一点，且使所得的黑弧的长度大于，乙获
胜．
答 案
见解析
解析
解：甲没有必胜策略．
分两种情况讨论．
(i)若甲第一步选择分组操作，则乙第一步也选择分组操作，且乙操作时分出一个只有枚棋子的
组．这样在乙操作后，甲乙两人均无法进行取子操作了．之后，两人只能轮流进行分组操作，而从
现在的个组到最后分成
个组(每组一枚棋子)，还能操作
次．因此，最后一次进行
操作的是乙，从而乙获胜．
(ii)若甲第一步进行取子操作，则乙第一步还是选择分组操作，其只需仍分出一个只有枚棋子的
组．类似地，之后两人只能轮流进行分组操作，而分组操作还能再进行
次．因
此，最后一次进行操作的还是乙，乙仍获胜．
答 案
见解析
解析
解：若初始状态时，棋子总数
，为了便于讨论，不妨设
．
1
2
3
( )
n
1
n
n
2n −1
2n
n
n
1
n
k
1
( )
n
1
n
2
( )
k
n
1
n
1
n
1
n
1
d <
n
1
3
( )
d
例题4
1
9
49
49 −9 = 40
1
49 −7 −8 = 34
N =
n
i=1
∑
M
i
1 ⩽n
⩽
1
n ⩽
2
⋯⩽n
M
(i)当
与
的奇偶性不同(即
为奇数)时，甲只要第一步进行分组操作，且分出一组只有
枚棋子，之后，两人则只能轮流进行分组操作，而分组操作还能进行
(偶数)次．因
此，最后一次分组操作由甲完成，从而，甲获胜
(ii)当
与
的奇偶性相同时，为了避免输掉游戏，甲第一步必会采用取子操作(否则，乙只需按
中(i)的方式就可获胜)．当乙开始操作时，其面对的情况是
枚棋子被分成了
组．
若
与
的奇偶性不同，即
为奇数时，可化归到
中(i)的讨论，乙会获胜．
若
与
的奇偶性相同，即
为偶数时，类似于
中(ii)中前面的讨论，知乙为了不输，只
能进行取子操作．在这种情况下，甲乙两人首先会轮流进行
次取子操作(此时会有一组中的
棋子个数变为，取子操作无法继续)，之后，两人会再轮流进行
次分组操作．由于
为偶数，于是，谁先第一个进行分组操作，谁就会输掉游戏因此，讨论
的奇偶性，知
为偶数时，甲将获胜；
为奇数时，乙将获胜．
综上，本题的结论为
与
的奇偶性不同时，甲获胜；
与
同为奇数时，乙获胜；
与
同为
偶数时，若
为偶数，则甲获胜，若
为奇数，则乙获胜．
答 案
见解析
解析
解：乙有必胜策略．
图中画出了八条好对角线．
若乙每次均不染这八条对角线经过的方格，则甲至少要染八次才能获胜．
下面证明：乙至多染七次就可获胜．不妨设甲第一次染的是左上角的
子方格表内的一个小
格．将此
的子方格表内的
个小格按图赋值．
若甲第一次染的是填有的小格，则乙也染另一个填有的小格．然后，乙至多再染两次，就可使
此
子方格表的每行、每列均至少含有一个黑格，这也保证了前四列和上面四行的每行、每列
均至少含有一个黑格．
乙至多只需染四次(每次染的小格不同行也不同列)，就可使右下角的
子方格表的每行、每列
各有一个黑格．
因此，乙至多只需染七次就可使每行、每列各含一个黑格．
综上，乙有必胜策略．
1
N
M
N −M
1
N −M −1
N
M
2
( )
N −M
M
N −M
M
N
2
( )
N −M
M
N
2
( )
n
−
1
1
1
N −n
M
1
N −n
M
1
n
1
n1
n1
N
M
N
M
N
M
n1
n1
例题5
4 × 4
4 × 4
16
x
x
4 × 4
4 × 4
答 案
见解析
解析
解：当且仅当
时，乙有必胜策略．
当
，时，显然甲获胜．
当
时，记
表示一个边长为的正边形，表示由
的所有边和对角线组成的集合．则全部
交点可以用集合
表示，即用，，
，给正边形
的顶点编号，分别表示题中的
个圆，用
表示集合中连接顶点、的线段．于是，圆与圆
的交点就和集合
中的元素
与
建立了对应关系．
接下来，只需将集合
中的元素两两分组，使得同组的元素
、
中的与
端
点均不一样．若存在这样的分组，则乙在每个回合只需将甲取走的硬币的同组硬币取走即为必胜策
略．
下面构造这样的分组．
先按照如下规则建立双射
：
．
若为正边形
的边，则将其绕正边形
的中心逆时针旋转
弧度得到
；若为正边形
的对角线，则将其绕正边形
的中心逆时针旋转
弧度得到
．
当
时，与
彼此端点均不同．接下来，将
与
分在同一组，即完成构
造．
答 案
见解析
解析
解：，，，，，，
，
，，，
，．
答 案
见解析
解析
解：记
表示好排列构成的集合，
表示，，
，
按以下要求填到正
边形
的顶点上的方案构成的集合：
(i)填在多边形外接圆直径两端的数字之和为
；
(i)不存在若干相邻顶点，其和为
的倍数．
于是，只需证明集合
、
之间存在双射，及
．
1
1
2
例题6
n ⩾4
n = 2
3
n ⩾4
P
1
n
S
P
S × 0, 1
{
}
1
2
⋯
n
n
P
n
ei,j
S
i
j
i
j i=
j
( / )
S × 0, 1
{
}
e
, 0
( i,j
)
e
, 1
( i,j
)
S × 0, 1
{
}
e, ε
(
)
e , ε
( ′
′)
e
e′
F
S →S
e
n
P
n
P
n
4π
F e
( )
e
n
P
n
P
n
2π
F e
( )
n ⩾4
e
F e
( )
e, 0
(
)
F e , 1
(
( )
)
例题7
1
2
4
8
3
6
12
11
9
5
10
7
A
B
1
2
⋯
2n
2n
X
X
⋯X
1
2
2n
2n + 1
2n + 1
A
B
A =
∣∣
B >
∣
∣
0
从
中选取一个好排列
，对每个
，记
，
其中，
，
，且满足
．
易知，
两两不等．
将这些数字依次填在正
边形的顶点上．则
．
由于
，于是，
．
注意到，
，
及
彼此不等．
则不存在、使得
．
从而以上填数方案在组合
中．
从集合
中选择一个填数方案，构造如下排列：
，
其中，
，
．
显然，
两两不同．
对于任意的
，由
．
则对所有的
，
模
的余数均相等，记为．
故
．
又因为
，所以，
，即
．
因此，这个填数方案是一个好排列．
至此，建立了集合
、
之间的双射．
易知，满足
的填数方案有
种，记它们构成集合．
中的某些填数方案存在相邻的个顶点，其数字之和为
的倍数，显然，
．
将所有这样的个数字组成的数组记作集合
．
注意到，这相邻的个顶点的起始点有种可能，而余下的
个数有
种填法，
则
．
又集合
中的每个方案均可看成是对于集合
的任意一个
元子集，给其添加
一个余下的数字，使得数字之和为
的倍数．
显然，这样的添加方法至多一种．
故
．
由
A
a
, a
, ⋯, a
( 1
2
2n)
1 ⩽i ⩽2n
b
≡
i
a
−
i+1
a
mod2n + 1
i (
)
a
=
2n+1
a
1
b
=
2n+1
b
1
b
∈
i
1, 2, ⋯, 2n
{
}
bi
2n
b
+
i
b
≡
i+n
a
−
i+1
a
+
i
a
−
i+1+n
a
i+n
= 2 2n + 1 ≡
(
)
0 mod2n + 1
(
)
0 < b
+
i
b
<
i+n
2 2n + 1
(
)
b
+
i
b
=
i+1
2n + 1
a
=
i
a
+
1
a
−a
k=1
∑
i−1
( k+1
k)
≡a
+
1
b
mod2n + 1
k=1
∑
i−1
k (
)
ai
i
j
a
−
j
a
≡
i
b
≡
k=i
∑
j−1
k
0 mod2n + 1
(
)
B
B
a
≡
i
b
mod2n + 1
k=1
∑
i
k (
)
1 ⩽a
⩽
i
2n
i = 1, 2, ⋯, 2n
ai
2 ⩽i ⩽n
b
+
i
b
≡
i+n
a
−
i
a
+
i−1
a
−
i+n
a
i+n−1
≡0 mod2n + 1
(
)
⇒a
+
i
a
≡
i+n
a
+
i−1
a
mod2n + 1
i+n−1 (
)
1 ⩽i ⩽n
a
+
i
a
i+n
2n + 1
a
a
+ a
=
i=1
∑
n
( i
i+n)
k ≡
k=1
∑
2n
na mod2n + 1
(
)
n, 2n + 1 =
(
)
1
a = 0
a
+
i
a
=
i+n
2n + 1
A
B
b
+
i
b
=
i+n
2n + 1
n! ⋅2n
S
S
k
2n + 1
k ⩾3
k
S
k
k
n
2n −2k
2
n −k !
n−k (
)
S =
∣∣
n
2
n −k ! S
k=3
∑
n
n−k (
) ∣
k∣
S
k
1, 2, ⋯, 2n
{
}
k −1
2n + 1
k S
⩽
∣
k∣
1 ⋅C
2n
k−1
C
÷
2n
k
C
=
n−1
k
C
÷
k
2n −k + 1
2n
k−1
C
k
n −k
n−1
k−1
，
利用数学归纳法容易证明：对所有的
，
，
，均有
．
综合上面结论及不等式
，有
．
因此，
，即存在好排列．
答 案
见解析
解析
解：将五块蛋糕分别记为
，
，
，
若阿拉士能够得到
、
或
、
，则他获胜，即阿拉士至少获得一半的蛋糕(因为巴赫拉姆最终
恰得到两块蛋糕且他得到蛋糕的重量的和一定小于蛋糕重量的一半)．
共有四种可能的蛋糕排列，以下对每一种可能分别说明阿拉士的获胜方案．
与
、
相邻．
阿拉士为了获胜，先取
，他下一次取蛋糕时取出
或
即可．
、
相邻但
不在中间．
阿拉士可以利用类似
的策略，即先取
，下一次取蛋糕时取出
或
．
不与
、
的任何一块相邻．
阿拉士可以利用类似
的策略，即先取
，下一次取出
或
．
与
、
中恰一块相邻．
此时，获胜的策略取决于
、
的总重量．
若
、
总重量小于整个蛋糕的一半，则阿拉士先取
，这表明，巴赫拉姆最佳的方案是拿到
、
，但
小于蛋糕的一半．
若
、
总重量大于蛋糕的一半，则阿拉士先取
、
中不与
相邻的那块，然后等下一轮时，
他取
或
、
中的另一块即可．
综上，无论最初怎么分配，阿拉士都有满足要求的办法．
1
=
C
÷ C
n −k
2n −k + 1 (
2n
k−1
n−1
k−1)
< 4 C
÷ C
(
2n
k−1
n−1
k−1)
n ⩾5
k ⩾3
n ⩾k
C
⩽
2n
k−1
4
C
k−1
n−1
k−1
<
k=0
∑
n
k!
xk
ex
S ⩽
∣∣
n
2
n −k !
C
k=3
∑
n
n−k (
) k
1
2n
k−1
⩽n
2
n −k !
C
4
k=3
∑
n
n−k (
) k
1
n−1
k−1
k−1
= 2 n!
n
4
1
k=3
∑
n
k!
2k
< 2 n!
n
4
e −1 −2 −2
2
< 2 n!
n
A =
∣∣
B =
∣
∣
2 n! −
n
S >
∣∣
0
例题8
p1
p2
⋯
p
p
< p
< p
< p
< p
5 ( 1
2
3
4
5)
p4
p5
p3
p5
1 p
( )
5
p
3
p
4
p5
p3
p4
2 p
( )
3
p
5
p
5
1
( )
p4
p3
p4
3 p
( )
5
p
3
p
4
1
( )
p5
p3
p4
4 p
( )
5
p
3
p
4
p3
p4
p3
p4
p5
p3
p4
p
+
3
p
4
p3
p4
p3
p4
p5
p5
p3
p4
