数学竞赛中的反证法

反证法的证题模式可以简要地概括为“否定推理否定”.即从否定结论开始，经过正确无误的推理导致逻辑矛盾，达到新的否定，可以认为反证法的基本思想就是“否定之否定”.应用反证法证明的主要三步是：否定结论推导出矛盾结论成立.

在应用反证法证题时，一定要用到“反设”进行推理，否则就不是反证法.用反证法证题时，如果欲证明的命题的方面情况只有一种，那么只要将这种情况驳倒了就可以，这种反证法又叫“归谬法”；如果结论的方面情况有多种，那么必须将所有的反面情况一一驳倒，才能推断原结论成立，这种证法又叫“穷举法”.

例1 证明当p, q均为奇数时，曲线y=x2-2px+2q与x轴的交点横坐标为无理数.(2009清华大学夏令营选拔考试)

思路分析

要说明二次方程无有理解，目前倒没有什么直接的判断方法，因此采用反证法.

证明

反设交点横坐标为有理数，即存在交点横坐标为x=uv ((u, v)=1)，则uv2-2puv+2q=0，即u2-2puv+2qv2=0， u2=2(puv-qv2)①为偶数，于是u为偶数.

又(u, v)=1，得v为奇数.

另外由①有v|u2，从而v|u.又(u, v)=1，得v=1.

设u=2s，则4s2-4ps+2q=0，即2s2-2ps+q=0， q=2(ps-s2)为偶数，与已知条件的奇偶性矛盾.

从而反设不成立，说明结论成立.

即曲线y=x2-2px+2q与x轴的交点横坐标为无理数.

解题回顾

在简单整数理论中，反证法是常用的方法.主要适用的情况就是我们正面不能处理的时候，来假设结论不成立，利用假设作为条件，通过推演出矛盾，最终否定假设.在简单整数理论中，很多时候推出的矛盾是奇偶矛盾，比如说最经典的反证法证明2是无理数.

例2 已知1与90之间的19个（不同的）正整数，两两的差中是否一定有三个相等？（1990年匈牙利数学竞赛题）

分析

这类问题要从正面来处理，非常困难.可考虑从反面出发：没有三个相等的情况，最多两个相等，从而我们能得到怎样的信息呢？如果按大小顺序排列的话，那么产生18个差，这些差至多两个相等，也就形成了一些重叠，从而至少有9个不同的数，于是设法找到存在性或者矛盾的方面.

证明

设这19个数为1≤a1＜a2＜…＜a19≤90.

由于a19-a1=(a19-a18)+(a18-a17)+…+(a2-a1)，

反设右边的18个差中无三个相等，而只有两个相等，且取最小的，则

a19-a1＞2×(1+2+…+9)=90,

这与a19-a1≤90-1=89矛盾.所以反设不真.故两两的差中定有三个相等.

解题回顾

虽然从形式上来看没有用到“抽屉原理”，但用到了抽屉原理的思想，即18个数放到9个盒子中，最平均的情况就是每个盒子两个，否则就出现我们要证明的结果：三个数在一个盒子里，即存在三个差相等.由此，我们在讨论问题的过程中，不能仅仅盯着定理和原理能否使用，而是应该理解和挖掘定理和性质本身的数学思想，从而在解决问题的过程中灵活运用.

例3 已知以a1为首项的数列{an}满足：an+1=an+c， an＜3，and，an≥3.

当0＜a1＜1m（m是正整数）， c=1m， d≥3m时，求证：数列a2-1m， a3m+2-1m， a6m+2-1m， a9m+2-1m成等比数列当且仅当d=3m.（2008年上海高三数学竞赛试题）

思路分析

充分性证明“当d=3m时，数列a2-1m， a3m+2-1m， a6m+2-1m， a9m+2-1m成等比数列”它只要代入验证就可以了，没有任何的技巧和复杂的计算，必要性证明“已知数列a2-1m， a3m+2-1m， a6m+2-1m， a9m+2-1m成等比数列，求证d=3m”时，直接证明比较困难，我们要学会跳出正面冲突，从反面考虑问题，就可以找到解决问题的办法，基本的策略是列举法，找出矛盾，使问题得以解决.

证明

充分性略，下证必要性：反设d≥3m+1，

则有a1, a2=a1+1m, a3=a1+2m, …, a3m+1=a1+3mm=a1+3，

a3m+2=a1+3d＜1m, a3m+3=a1+3d+1m, …,

a6m+1=a1+3d+3m-1m＜3，

a6m+2=a1+3d+3＞3, a6m+3=a1+3d+3d＜1m, …,

a9m+1=a1+3d+3d+3m-2m,

a9m+2=a1+3d+3d+3m-1m＞2， ….

所以a2-1m＞0, a3m+2-1m＜0, a6m+2-1m＞0, a9m+2-1m＞0.

故数列a2-1m， a3m+2-1m， a6m+2-1m， a9m+2-1m不是等比数列.

所以，数列a2-1m， a3m+2-1m， a6m+2-1m， a9m+2-1m成等比数列时，d=3m.

解题回顾

正难则反，是数学解题一个规律.正面解决困难的时候,我们有必要调整方向,从问题的反面入手,相当于增加了一个条件,在本题中d≥3m+1比d=3m要收缩的多,数列增加就慢了,所以原来d=3m时刚好是满足的,现在就要向后推移了,自然就应当存在矛盾,这时直觉的定性分析也帮上了忙.

例4 证明如果在取三个不同的整数值时，变量x的整系数多项式的值的绝对值都是1，那么这个多项式没有整数根.（2005年江苏竞赛初赛题）

证明

设整系数多项式f(x)对于三个不同的整数a, b, c有

|f(a)|=|f(b)|=|f(c)|=1.(1)

假定f(x)有整数根x0，则f(x)=(x-x0)Q(x). (2)（这里Q(x)是整系数多项式）

由(1)(2)可知，|(a-x0)Q(a)|=|(a-x0)||Q(a)|=1.

由于Q(a)是整数，则|a-x0|=1，同理|b-x0|=1, |c-x0|=1.

从而三个数a-x0, b-x0, c-x0中必有两个相等，因此a, b, c中某两个相等.

这与已知矛盾，从而f(x)没有整数根.

解题回顾

(1) 运用了性质：多项式f(x)，对于a, b∈R, a≠b， a-b必为f(a)-f(b)的因子；

（2） 研究含有否定词“不存在”，“没有”，“不相等”，“不可能”等有关命题时，我们常用的策略是从反面考虑问题，即正难则反.

例5 已知函数f(x)=ax2+bx+c (a≠0)，且f(x)=x没有实数根，问：f(f(x))=x是否有实数根？并证明你的结论.（2009年上海交大自主招生试题）

解析

反证法.若存在f(f(x0))=x0，令f(x0)=t，则f(t)=x0，即(t, x0)是y=f(x)图象上的点.又f(x0)=t，即(x0, t)也是y=f(x)图象上的点.显然这两点不重合，且这两点关于直线y=x对称.而y=f(x)=ax2+bx+c是连续函数，故y=f(x)=ax2+bx+c与y=x必有交点，从而f(x)=x有实数解，矛盾！

解题回顾

利用反证法，使问题的解决直观明了.同时，本题的结论对一般的连续函数f(x)也成立，其运用的处理方法，是可以值得借鉴.

例6 （2008年北大自主招生试题）实数ai(i=1, 2, 3), bi(i=1, 2, 3)满足a1+a2+a3=b1+b2+b3， a1a2+a2a3+a3a1=b1b2+b2b3+b3b1， min(a1, a2, a3)≤min(b1, b2, b3).

求证：max(a1, a2, a3)≤max(b1, b2, b3).

思路分析

本题直接证明十分困难，于是我们想到正难则反，利用反证法，结合函数构造，来完成证明.

解析

不妨设a1≤a2≤a3, b1≤b2≤b3，则a1≤b1.下证a3≤b3.用反证法.若a3＞b3，构造两个函数f(x)=(x-a1)(x-a2)(x-a3), g(x)=(x-b1)(x-b2)(x-b3).由已知条件a1+a2+a3=b1+b2+b3， a1a2+a2a3+a3a1=b1b2+b2b3+b3b1，知f(x)=g(x)+b1b2b3-a1a2a3.一方面f(a1)=g(a1)+b1b2b3-a1a2a3=0， f(a3)=g(a3)+b1b2b3-a1a2a3=0，故g(a1)=g(a3).另一方面，g(a1)=(a1-b1)(a1-b2)(a1-b3)， a1-b1≤0, a1-b2≤0， a1-b3≤0，所以g(a1)≤0；而g(a3)=(a3-b1)(a3-b2)(a3-b3), a3-b1＞0, a3-b2＞0， a3-b3＞0,所以g(a3)＞0，这与g(a1)=g(a3)矛盾.故a3≤b3, max(a1, a2, a3)≤max(b1, b2, b3).

解题回顾

数学竞赛考试是智慧的较量，尤其是面对困难如何摆脱的智慧.现在的数学竞赛、自主招生考试、高考必然出现“生题”“新题”，对此考生可能一时无法把握，使思考困顿，解题停顿.这些战略高地以单一的方式一味死攻并非上策，要学会从侧翼进攻，要有“战略迂回”的意识从侧面或反面的某个点突破，往往会出奇制胜.本题思维要求高，是一道难度较大的试题.

牛顿曾经说过：“反证法是数学家最精当的武器之一”.一般来讲，反证法常用来证明的题型有：命题的结论以“否定形式”、“至少”或“至多”、“唯一”、“无限”形式出现的命题；或者否定结论更明显、具体、简单的命题；或者直接证明难以下手的命题，改变其思维方向，从结论入手进行反面思考，问题可能解决得十分干脆.

巩固训练

1 证明：若f(f(x))有唯一不动点，则f(x)也有唯一不动点.（2010年浙江大学自主招生试题改编）

2 已知函数f(x)=13x3-2x2+3x （x∈R）的图象为曲线C,求证不存在一条直线与曲线C同时切于两个不同点.（2009年东南大学自主招生试题）

3 已知有整系数a1, a2, …, an的多项式f(x)=xn+a1xn-1+…+an-1x+an，对四个不同的整数a, b, c, d使得f(a)=f(b)=f(c)=f(d)=5，证明：不存在整数k使得f(k)=8.（2009年四川竞赛初赛题）

3 设f(x)=ax2+bx+c，已知f(1), f(2), f(3), f(4), f(5)都是质数，求证：f(x)不能分解成两个整系数的一次式的乘积.（2010年福建数学竞赛初赛题）

1 证明：不妨设x0是f(f(x))的唯一不动点，即f(f(x0))=x0，令f(x0)=t，则f(t)=x0，那么，f(f(t))=f(x0)，而f(x0)=t，即f(f(t))=t，这说明t也是f(f(x))的不动点.有f(f(x))有唯一不动点，知x0=t，从而f(t)=t，这说明t也是f(x)的不动点，存在性得证.

下证唯一性.假设若f(x)还有另外一个不动点t0，即f(t0)=t0 (t≠t0)，那么f(f(t0))=f(t0)=t0，这说明f(f(x))还有另外一个不动点t0，与题设矛盾.

解题回顾 当f(x0)=x0时，我们称x0为函数f(x)的不动点.利用不动点原理可以解决某些数学问题，它是自主招生考试中的热点问题.

2 证明：反设存在过曲线C上的点A(x1, y1)的切线同时与曲线C切于两点，另一切点为B(x2, y2)， x1≠x2.

则切线方程是：y-13x31-2x21+3x1=(x21-4x1+3)(x-x1)，

化简得：y=(x21-4x1+3)x+-23x31+2x21.

而过B(x2, y2)的切线方程是y=(x22-4x2+3)x+-23x32+2x22，

由于两切线是同一直线，

则有：x21-4x1+3=x22-4x2+3，得x1+x2=4.

又-23x31+2x21=-23x32+2x22，

即-23(x1-x2)(x21+x1x2+x22)+2(x1-x2)(x1+x2)=0，

-13(x21+x1x2+x22)+4=0，即x1(x1+x2)+x22-12=0，

即(4-x2)×4+x22-12=0， x22-4x2+4=0，得x2=2.

但当x2=2时，由x1+x2=4得x1=2，这与x1≠x2矛盾.

所以不存在一条直线与曲线C同时切于两点.

3 分析：注意到a, b, c, d是多项式f(x)-5的根，于是可以构造一个多项式f(x)-5，再利用因式定理，结合反证法得到证明.

证明：由已知，应有f(x)-5=(x-a)(x-b)(x-c)(x-d)g(x)，其中g(x)是整系数多项式.

如果有整数k使得f(k)=8，即(k-a)(k-b)(k-c)(k-d)g(k)=3.

但素数3不能有4个以上不同的因数，从而矛盾，

故不存在整数k使得f(k)=8.

3 反设f(x)=g(x)h(x)，其中g(x), h(x)都是整系数的一次式.

则f(1)=g(1)h(1)， f(2)=g(2)h(2)， f(3)=g(3)h(3)， f(4)=g(4)h(4)， f(5)=g(5)h(5)，

这上述5个等式的左端都是质数，因此g(1), g(2), g(3), g(4), g(5), h(1), h(2), h(3), h(4), h(5)中至少有5个是±1. 由于g(x)是整系数的一次式，因此g(1), g(2), g(3), g(4), g(5)是不同的数，即至多一个1，一个-1；同理h(1), h(2), h(3), h(4), h(5)中至多一个1，一个-1，矛盾.

所以反设不真，故原命题成立.