数学竞赛中常用方法和原理

数学竞赛中常用方法和原理
研究解题的方法和策略称为探索 . George Polya 提供的基本解题的探索可以分成以下几个类型 .
(1) . 建立模型 .
(2) . 问题的图示 .
(3) . 表征一个等价问题 .
(4) . 修改问题 .
(5) . 选取有效符号 .
(6) . 利用对称性 .
(7) . 分解一个问题成若干子问题 .
(8) . 反向推理 .
(9) . 奇偶性 .
(10) . 极值方法 .
(11) . 一般化 .
(12) . 数学归纳方法 .
(13) . 鸽龙问题 .
(14) . 数论方法 .
(15) . 复数方法 .
(16) . 代数方法 .
(17) . 级数求和 .
(18) . 函数方法 . ( 微分 , 积分方法 )
(19) . 不等式方法 .
(20) . 不等式中的函数方法 .
(21) . 几何方法 .
(22) . 组合数学方法 .
(23) . 图论方法 .
(1). 数学模型的建立 .
建立对问题的直接分析 , 从特殊到一般 .
例 : 证明 n 个不同元素的集合具有 n 2 个不同的子集 . 例 : 假设和为没有公因子的正整数 . 证明 :
2)
1)(1()1(2--=⎥⎦
⎤⎢⎣⎡-++⎥⎦⎤⎢⎣⎡+⎥⎦⎤⎢⎣⎡b a b a b b a b a 解 : 令 x b
a
x f =)( （why ?） 则 k b
a k f =)( 令 5=a , 7=b
⎥⎦
⎤⎢⎣⎡k 75 的几何意义—— )75,(k k P k 在直线 x y 75= 上 而 ⎥⎦
⎤
⎢⎣⎡k 75
表示 k P 下方介于 x 轴上之间格点的个数 . 从而
21
756
1=⎥⎦⎤⎢⎣
⎡∑=k k 矩形内格点数目 6421⨯⨯= 注 : 1)7,5(= , 所以矩形内部 x y 7
5
= 上无格点 .
一般地 , 1),(=b a 时 . 有 )1)(1(21
1
1--=⎥⎦
⎤
⎢⎣⎡∑-=b a k b a b k 这是一个典型的从特殊到一般的范例 . (2) . 图示法 .
例 : 假设 n m , 都是正整数且 n k ≤≤1 则有 ⎪⎪⎭
⎫
⎝⎛+=⎪⎪⎭⎫
⎝⎛-⎪⎪⎭⎫ ⎝⎛∑=k n m i k m i n k
i 0 右边是从一个 n m + 元集合中 S 取 k 个不同元的方法总数 . 将 S 分成两个子集 A 和 B . n A = ，m B = .
则 S 的每个 k 元子集 k S 中有 i 个元取自 A , 而 i k - 个元取自
B . )1(k i ≤≤ . 对 k i ,,2,1,0 = , 应用乘法原理 , 得右 = 左 .
(3) . 表示一个等价问题 .
例 : 设 ⎪⎭
⎫
⎝⎛++-=x x
x f 111121)( , 求 )(x f 的 n 阶导数 .
(4) . 修改一个问题 .
这个方法常用于不等式的证明中 . 例 : 设 +∈R b a , , 证明 : 2
)(b a b a ab b a +≥
解 : 11)
()
(2
2
2
≥⎪
⎭
⎫ ⎝⎛⇔≥⇔
≥-++b a b a b
a b
a b a b a ab b a ab b a
Case 1 . b a ≥ 时 . 12
≥⎪
⎭
⎫
⎝⎛-b a b a
Case 2 . b a < 时 . 12
≥⎪
⎭
⎫ ⎝⎛-b
a b a
(5) . 选取有效的符号 .
有效的符号可以消去符号的冗余 , 某些关系会显露出来 . 例 : 设 110<<-a , 定义递推公式
2
1121⎪⎭
⎫ ⎝⎛+=-n n a a n <0
又设 ()n n n a A -=14 , 当 ∞→n 时 , n A 趋向于什么 ? (6) . 利用对称性 . ( 不充分性推理原则 ) . 没有充分的理由说明存在差异就可能没有差异 . 例 : 在 1=+y x )0,0(>>y x 下 . 求 max { xy } .
例 : 在 121=+++n x x x )0(>i x 下 . 求 }min{22221n x x x +++
(7) . 分解一个问题成若干个子问题 .
经常需要将一个问题分解成若干个子问题 , 然后分别解决这些子问题 . 例 : 证明圆周角 2
1= 同弧所对圆心角 . (8) . 反向推理 .
Basic idea ---- 反向推理是假定结论成立 , 由结论来推出某些已知的或易于证明的东西 .
关键在于区分那些推理方向是可逆的 . 例 : 设 c b a ,, 为三角形三边长 , 证明 :
())(4)(32
ac bc ab c b a ac bc ab ++≤++≤++
(9) . 反证法 .
使用反证法是首先假设结论不成立 , 然后进行推理 , 直至推出和已知条件矛盾或某些正确结论矛盾 .
范围 : 当结论容易被否定 , 当给出条件不好利用 , 当思路不太明了 . 例 : 证明调和级数
+++++n
13
12
1
1 发散 . 证明 : 设其收敛于 r . 则有
+++++
=n r 1
31211 ++++++>)61
61()4141()2121( r n =+++++= 1
31211
矛盾 !
(10) . 奇偶性 .
例 : 设 n 是大于 1 的奇数 , A 是 n n ⨯ 对称矩阵且 A 的每一行 ,
列都是 n ,,2,1 的排列 , 证明 : n ,,2,1 中每一个数字都在主对角线上出现 .
(11) . 极值法 .
将问题置于某种极端情形下 , 所需要结构就会出现 . 从而使得问题的解决变得简单起来 .
例 : 平面上给定不是所有都共线的有限多个点 . 证明 : 存在只通过其中两点的直线 .
解 : 设 P 是一个点 , L 是一直线 . ),(L P d 是从 P 到 L 的距离 . 令 }0),({直线但至少过两个给定点的为不过取给定点集，P L P L P d S >= 则 φ≠S ( 因为所有点不会位于同一直线上 ) Claim : S 中有最小值 ),(L P d .
Claim : L 只过给定点中两个点 . 否则 , ∃ 三点 321P P P 、、 在 L 上 .
Q 是 P 在 L 上垂足 ， 不妨设 2P 在 Q 一侧 . 过 P 与 3P 可连
直线 1L t s ⋅ 12L P ∉ 且 ),(),(12L P d L P d < . 与 L 的定义相违 ! (12) . 问题的一般化 .
将一个特殊 , 具体的数学问题放入一个更加一般的环境下有两个好处 : 1 . 固有的规律会出现
2 . 更加强大的工具会派上用场 .
例 : 求和 ∑=⎪⎪⎭
⎫ ⎝⎛n
k k n k 0 )0(>n
解 ：引入函数 k n
k x k n k x f ∑=⎪⎪⎭
⎫ ⎝⎛=0)(
则 ∑=⎪⎪⎭
⎫
⎝⎛=n
k k n k f 0
)1(
只用求出 )(x f 即可 !
1
0)(-=∑⎪⎪⎭
⎫ ⎝⎛=k n
k x k n k x x f
'
0⎪⎪⎭
⎫
⎝⎛⎪⎪⎭⎫ ⎝⎛=∑=k n k x k n k x
()()()1'
11-+=+=n n x nx x x
故有 : 12)1(-=n n f
例 ：设有数列 ： ,,,3,2,132n n 求其最大项 }max {n n . (13) . 数学归纳方法 .
数学归纳法又称为完全归纳法 , 常用证明问题 .
优点 —— 使证明严谨 ; 缺点 —— 不能用于出现新的数学性质和命题 . (1)
. 基于 k P 的归纳证明 .
原理 —— step 1 . )(a P 正确 , ( a 是初值 ) .
step 2 . 如果以下过程是正确的 : 对 N n ∈∀ , 从 )(n P 正确能推出 )1(+n P 正确 . 则性质 P 对所有自然数都成立 .
例 : 平面内有 n 条直线 , 无两条平行 , 也无三点共线 . 试证 : 这
n 条直线将平面分成 1)1(2
1
++n n 个部分 .
例 : 对于自然数 n 和实数 x , 证明 :
[][]nx n n x n x n x x =⎥⎦⎤⎢⎣
⎡-++⎥⎦⎤⎢⎣⎡++⎥⎦⎤⎢⎣⎡++121 .
Basic idea ---- 对于固定 n 和区间 ⎪⎭
⎫
⎢⎣⎡+n k n k 1,
中所有 x , 结论成立 .
,2,1,0±±=k
0=k 时 . 01,0=⎥⎦⎤⎢⎣
⎡
+⇒⎪⎭⎫⎢⎣⎡∈n i x n x 11-≤≤n i
左 = 右 . 设 ⎪⎭⎫
⎢
⎣
⎡-∈n k n k x ,1 时有 [][]nx n n x n x n x x =⎥⎦⎤⎢⎣
⎡
-++⎥⎦⎤⎢⎣⎡++⎥⎦⎤⎢⎣⎡++121 现考虑 ⎪⎭⎫⎢⎣⎡+∈n k n k x 1,
. 令 n y x 1+= . 则 ⎪⎭⎫
⎢
⎣
⎡-∈n k n k y ,1 左 []⎥⎦⎤⎢⎣⎡-++⎥⎦⎤⎢⎣⎡++⎥⎦⎤⎢⎣⎡++=n n x n x n x x 121 []1121++⎥⎦⎤⎢⎣
⎡
-++⎥⎦⎤⎢⎣⎡++⎥⎦⎤⎢⎣⎡+=y n n y n y n y [][]==+=nx ny 1 右 .
由归纳法原理 , 结论对所有自然数 +∈R x k , 成立 . 类似可证 -∈R x 时 , 结论也成立 .
注 : 这个例子表明 , 在使用数学归纳法时 , 必须明确对什么东西进行归纳证明 . (2)
. 强归纳 .
原理 —— step 1 . )(a P 正确 .
Step 2 .如果以下过程正确 : 对 N n ∈∀ 从 )()1()(n a P a P a P ++、、
、 均正确 , 可以推出 )1(++n a P 也正确 . 则性质 P 对所有自然数 n 都成立 .
例 : 设 +∈R x . 证明 : [][][][]nx n
nx x x ≤+++
2
2 .
解 : 1=n 时 , 自然成立 .
假设不等式对于 k n < 的一切 n , 有
[]x a ≤1 []x a 22≤ []x k a k )1(1-≤-
这里 []∑
==i
j i j
jx a 1
. 累加后有
[][][]x k x x a a a k )1(2121-+++≤+++-
又 []kx a a k k k =--)(1 []x k a a k k k )1())(1(21-=----
[]x a =⨯11
相加后有 :
[][][][]kx x k x x a a a ka k k k +-+++=------)1(2121
[][][][][]121)1()(2a a a a kx x k x i k x x ka i k k k +++++++-++-+++=--
[][][][][][][][][]
x ix x k x k kx x k x i k x x ++++-+-++-++-+++≤ )2()1()1()(2 [][][][][][][]kx x i k ix ix x i k x i k ix =-+≤+-=-+)()()( []kx k ka k ≤∴
[]kx a k ≤∴
(14) .鸽笼原理 .
鸽笼原理是数学竞赛中常用的方法 , 其形式众多 , 常见的有以下形式 : (1)
. 最简单形式 —— 将 1+n 个物体放入 n 个盒子内 , 则有一
个盒子内有两个物体 .
例 ：边长为 2 的正三角形内任意放 5 个点,则其中有两个点之间距离不大于 1 .
注 : 发现和制造鸽子与笼子之间关系十分重要 . (2)
. 加强形式 —— 将 1)1(+-r n 个物体放入 n 个盒子内 , 则有
一个盒子内有 r 个物体 .
例 ：( 染色问题 ) 设有 6 个点 621x x x 、、
、 .在每一对节点 j i x x 、 之间连一线段 . 得到一个 6 阶完全图 6K , 现用 0 或 1 这两种颜色给
6K 的边染色 ，每一边只能接受一种颜色 . 证明 : 无论怎样给 6K 的
边染色 , 其中总有单色三角形 . (3)
. 统计形式 —— 设有 n 个非负实数 n m m m 、、
、 21 如果 r m m m n
n ≥+++)(1
21 . 则必有某 r m i ≥ . (15) . 数论方法 . (16) . 复数方法 .
复数涉及范围广 , 常用知识如下 : (1)
. 复数形式 :
θθθi i re i r b a z =+=+=)sin (cos (2)
. 开方运算 .
设有 )sin (cos θθαi r b a i +=+= 则 )2sin
2(cos n
k i n
k r n n π
θπ
θα+++= , 10-≤≤n k
(3)
De Moivre 定理 .
θθθθn i n i n sin cos )sin (cos +=+
例 : 按 θcos 展开 θ5cos .
例 ：求常数 6210a a a a 、、
、、 t s ⋅ 01566cos 5cos 6cos cos a a a a ++++=θθθθ
解 : )(2
1
cos θθθi i e e -+=
θθθθθ)6(6
6
6
666
2
1
)(21cos k i ik k k i i e e C
e e --=-∑=+=
θ)62(6
06
6
21-=∑=k i k k e C
()()()()θθθθk i k k i k C k k ---+=∑=6sin 6cos sin cos 216
06
6
()()()θθθθk k k k C k k -+-=∑=6sin sin 6cos cos 2
16
06
6
()θθ62cos 2
1
cos 6
06
6
6
-=∴∑=k C
k k
例 : 证明 4
sin
22
31πn C C n n
n
=+- 解 : 令 ()i i y +=
+=12
14
sin
4
cos π
π
则 ()n
n
n i n i n y +⎪⎭
⎫ ⎝⎛=+=1214sin 4cos ππ
比较两边的实部后 , 有 (
)
)2(mod 0},Re{4cos 20
≡=∑=k i C n n
k k
k n n
π
+-+-=6421n n n C C C (
)
)2(mod 1},Im{4sin 20
≡=∑=k i C n n k k
k n n
π
+-+-=7531n n n n
C C C C 例 : 多项式 0,)(12211≠+++++=---n n n n n n a a x a x a x a x x f 如果 ()()112422531≤++-+++- a a a a a 则 )(x f 必有虚部不为零的复根 .
解 : ()()11)(24225312
≤++-+++-= a a a a a i f
由代数基本定理 , )(x f 可以完全分解为 ()j n j x x f α-∏==1)( 从而
()∏=-=n
j j i i f 1)(α C j ∈α
∏=+=n
j j i f 1
22
1)(α
如果 1)(2
≤i f , 则 n ααα、、
、 21 中一定有虚部不为零的复数 . ( 否则 , 由 1)(0002
2>⇒>⇒≠⇒≠i f a j j n αα .) (17) . 代数方法 . ( 1 ) . 因式分解 . 常用公式:
))((121---+++-=-n n n n n b b a a b a b a
)2)(222b ab a b a ++=+
例 : 证明 42024+-n n 是合数 , 其中 N n ∈ .
Basic idea —— 将 42024+-n n 进行因式分解 ( 如下 ) ()()()22
222424421644420n n n n n n n --=-+-=+-
()()
242422---+=n n n n
例 : 证明下面数列中每一个数都是合数 ,
,0011000100010,100010001,10001
解 : 原数列为 :
,1010101,10101,1011284844++++++ 考虑更为一般情形 :
,1,,1,1,14841284844n x x x x x x x x x ++++++++++ Case 1 . 12+=m n
)12(4841+++++m x x x
m x x x x x 84484)1()1(1++++++=
)1)(1(884m x x x ++++= . Case 2 . m n 2=
)2(4841m x x x ++++
()()()()()()
()()2
22
122
1244
124
1
2411111111x x x x x
x x x m m m m +-+-=--=--=
++++ ()()()()()()
2
2
1
221
221111x x x x m m +-+-=
++
()
(
)()
()m
m
x x x
x x x 22
42
224211+++-++++=
综上所述 , 上述数列中每一个数都是合数 . ( 2 ) . 多项式的唯一因式分解 .
核心定理 1 —— 设 )(x f 是一个多项式 . ())(0)(x f x f αα-⇔= 核心定理 2 ( 代数基本定理 ) . 复数域上的多项式可以完全分解 . 推论 1 —— 实数域上多项式不可约因式次数 2≤ . 核心定理 3 —— 欧几里德除法 .
例 : 求多项式 )(x P t s ⋅ ())(12x P x + , ()()1)(123+++x P x x 解 : )(),(x T x S ∃ t s ⋅
)()1()(2x S x x P +=
)()1(1)(23x T x x x P ++=+
e i ⋅ ()1)(1)()1(223=+-++x S x x T x x
运用欧几里德除法 , 求 )(),(x T x S .
()
)(1)1(1223x x x x x -+++=++ 1)(12+--=+x x x
())(112x x x -++=
(){})1)(1(112232++-++++=x x x x x x ())1)(1(12223+--+++=x x x x x x 取 x x T =)( , 1)(2-+=x x x S , 则
)1)(1()(22-++=x x x x P
例 : 证明对每个自然数 n , 1
322
42+++n n n
n 是不可约分数 . 解 : 只用证明 ()12,13gcd 324=+++n n n n 就可以 . ()()12132324+++=++n n n n n n ()n n n n n ++=+1223 112+=+nn n
1⨯=n n
()12,13gcd 324=+++∴n n n n 注 : 这是个多项式问题 . ( 3 ) . 两多项式恒等条件 .
核心结果 —— )(0)(x f x f ⇔≡ 的每个系数为 0 . 核心结果 —— ∑==n
i i i x a x f 0)( ()n x f =)(deg .
如果 )(x f 在 1+n 个不同点上为零 , 则 0)(≡x f .
推论 —— 两个 n 次多项式 )()()(x f x g x f ⇔≡ 与 )(x g 中每个 i x 系数相同 .
注意 —— 此性质常用来证明组合恒等式 . 例 : 如果 +∈N n m , 且 n k ≤≤1 , 证明
⎪⎪⎭
⎫ ⎝⎛+=⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-∑=k n m r n r k m k
r 0 例 : 设)(x f 是一个98次多项式 t s ⋅ k
k f 1
)(= , 991≤≤k . 求 )100(f . 解 : 1)()(-=x xf x g , 则有 ()99)(deg =x g , 0)(=k g , 991≤≤k ()∏=-=99
1)(k k x c c g
x
x g x f 1
)()(+=
, )0()(lim 0
f x f x =→
1)0()(lim 0
-==∴→g x g x , ()01!99199
=+⨯-∴c , !
991
=
c . ()⎭
⎬⎫⎩⎨⎧+-=∏=99
11!9911)(k k x x x f , ⎭
⎬⎫
⎩⎨
⎧+=
1!9911001)100(f . (18) . 级数求和 .
数列求和是数学竞赛的基本问题之一 , 主要有以下几个方面 . ( 1 ) . 二项式系数求和 . ( 2 ) . 等比数列求和 .
例 : 求和 θθθn cos 2cos cos +++ .
例 : 设 13,211+==+k k a a a 求和 n a a a +++ 21 .
解 : ⎪⎭
⎫
⎝
⎛+=++2132
11k k a a
( 3 ) . 交叉消去法求和 . 例 : 求和 : ()
∑
=+++n
k k k k k 0111
解 : 令
()
1
1111)
1(11
111
+-
=+-+=+++=
+++k k
k
k k k k k k k k k k k
1
11+-=n S n
(19) . 函数方法 .
函数方法是建立在连续数学与离散数学之间的桥梁 , 一个离散问题往往将其放入更大而广泛环境下 , 会显露其基本特征 , 导致问题的顺利解决 .
例: 设有数列 ,,,3,2,132n n 求其最大项 {}n n max .
解 : 引入函数 x x x f =)( 1≥x 令
0)
()
(=x f x df , 求得唯一驻点 e x =0 , 因而有 {}{}33233,2max max ==n n 例 : 求和 ∑=n
k k n kC 0 ()1≥n
解 : 引入函数 10
)(-=∑=k n
k k n x kC x f ,
则 ()1
1)(-+=n x n x f , 令 1=x 有 ∑=-⨯=n
k n k n n kC 0
12 .
(20) . 不等式方法 . 基本不等式 :
( 1 ) . 柯西不等式 :
∑∑∑===≤⎪⎭
⎫ ⎝⎛n
k k n k k n k k k b a b a 1212
2
1
对 R b a i i ∈∀, 成立 , 等式成立 ()()n n b b b a a a ,,,,,2121 ⇔ ( 2 ) . AM ——GM 不等式 ：
n
n n x x x n
x x x 2121≥+++ 对 +∈R x i 成立 .
例 : 设 +∈R c b a ,, , t s ⋅ ()()()8111=+++c b a 证明 : 1≤abc . 解法1 : ()()()()()abc ac bc ab c b a c b a +++++++=+++1111
33abc c b a ≥++
32223c b a ac bc ab ≥++ abc c b a abc +++≥∴322233318 ()
3
3
1abc +=
1≤∴abc
解法2 ：()()()c b a c b a 222111⋅⋅≥+++
1≤∴abc
例 : 求函数 ()31)(x x x f -= 当 10≤≤x 的最大值 . 解 : ()31)(x x x f -=
()()()
()()(
)4
33333
3333411131113)(3⎪⎪
⎭
⎫
⎝
⎛-+-+-+≤---=x x x x x x x x x f 316163)(≤
x f , 341=x 时 3max 1616
3
=f .
(21) . 不等式中的函数方法 .
凸函数方法是函数不等式研究的基本函数 .
)(x f 在 []b a , 上是凸的 )(x f ⇔ t s ⋅ Jensen 不等式如下 : )()()()(22112211n n n n x f x f x f x x x f λλλλλλ+++≤+++
这里 , 0,121≥=+++i n λλλλ .
判别方法 —— 如果 0)("≥x f , 则 )(x f 在 []b a , 上是凸的 . 例 : Lnx x f y ==)( , 0>x . 解 ：01
)(2
''<-
=x x f , )(x f 在 ()+∞,0 上是凹的 .
n n n n Lnx Lnx Lnx x x x Ln λλλλλλ+++≥+++ 22112211)(
令 n
n 121====λλλ , 则有
n
n n x x x n
x x x 2121)≥+++ .。