本
文
摘
要
反正法是数学竞赛中一种常见的证明方法，以下是 *** 中的描述：
反证法（又称背理法）是一种论证方式，他首先假设某命题成立（即在原命题的条件下，结论不成立），然后推理出明显矛盾的结果，从而下结论说原假设不成立，原命题得证。这里我们可以举两个经典的例子演示一下，利用反证法证明“素数有无穷多个”和“ 2\sqrt{2} 是无理数”。
（1）证明：素数有无穷多个
假设素数有有限多个.
不妨设为p1,p2,…,pnp_1,p_2,\ldots,p_n .
考虑p=p1p2p3…pn+1p=p_1p_2p_3\ldots p_n+1 .
显然，对于任意 pi,i=1,2…np_i,i=1,2\ldots n ,不能整除pp .
所以，构造出来的pp 是素数.
又因为p≠p1,p2,…,pnp \neq p_{1}, p_{2}, \dots, p_{n} ，
于是产生矛盾，
故原假设错误，素数有无穷多个。（2）证明： 2\sqrt{2} 是无理数
假设2\sqrt{2} 是有理数.
不妨设 2=pq\sqrt{2}=\frac{p}{q} ，其中p,qp,q 为互质的正整数.
两边平方化简可得，2q2=p22 q^{2}=p^{2} .
所以 pp 为偶数，不妨设 p=2kp=2k ，其中kk 为正整数.
所以 2q2=(2k)22 q^{2}=(2 k)^{2} ，化简可得q2=2k2q^{2}=2 k^{2} .
因此，qq 也是偶数.
但是这与p,qp,q 互质矛盾，
故 2\sqrt{2} 是无理数.可以发现反证法的一般步骤就是：先假设原命题不成立，然后在此基础上进行推理，接着得到矛盾，可能是与已知条件矛盾或者是与已知的定理矛盾，从而论证了原命题成立。
反证法的步骤还是比较清晰明了的，关键的好处是：增加了条件。有些命题很简洁，简洁到无法下手，比如上述两个命题“素数有无穷多个”和“ 2\sqrt{2} 是无理数”，但是通过反证法我们可以把结论变成条件，那么就有了下手的点，就比较好处理了。
在竞赛中遇到无从下手的问题不妨用反证法试试。
下面是2016DMM杜克数学竞赛团队赛第1题：
（3）2016-DMM-Team Round-1
题意:用“T”型去覆盖一个 6×66\times6 的网格，不允许重叠，请问最多能放多少个“T”型？根据题意，“T”型的个数 n≤6×64=9n\leq\frac{6\times6}{4}=9 ,下面我们给出了8个“T”型的一种放法。
那么会有9个“T”型的放法吗？
其实是没有了，最多8个，那么我们怎么证明呢？那么这里我们就要用到反证法。
假设有一种放法能够在6×66\times6 的网格中放下9个“T”型。
这里我们先给6×66\times6 的网格进行如下着色可以发现1个“T”型放到如上的网格中，每次都只能覆盖1个或者3个白色方格，于是按照9个“T”型覆盖的白色方格总数应该是一个奇数(奇数个奇数和为奇数)。
但是，我们从6×66\times6 网格的着色可以发现，白色方格的总数为18是一偶数，产生了矛盾。
故原假设不成立，不存在一种放法把网格填满。至此，我们证明了9个不行，又给出了8个的一种放法，那么最多就只能放8个了。
类似的还可以看下面这道题，2018DMM杜克数学竞赛团队赛第8题：
（4）2018-DMM-Team Round-8
题意：在一个圆上有7个点，每个点相距1个单位，且按逆时针标上了0，1，2，……，6。Feng从0开始，逆时针跳，一共跳了6次，标有1到6的点都经过一次，步长分别为 a1,a2,…,a6a_{1}, a_{2}, \dots, a_{6} 且各不相同。令 ss 表示 aia_i 中最大的数，其中 i=1,2…6i=1,2\ldots6 ，问 ss 最小是多少。这个题目有点绕，不过我们可以随意给出一种走法：
比如从0开始第一次走到标号1点，那么 a1=1a_1=1 ;
又因为 a1=1a_1=1 ， a2≠a1a_2\neq a_1 ,所以可以 取a2=2a_2=2 ，到标号3点；
按照0->1->3->6->4->5->2依次走下去，会发现刚好是满足题意的一种走法，各步长分别为 1,2,3,5,8,41,2,3,5,8,4 。那么根据定义 s=8s=8 。
当然还会有其他的走法，所以 ss 的取值有很多，而题目就是问其中最小的是多少。
这里我们给出了一种走法最小值是8，那么有没有可能最小值小于8呢？
其实是不存在的，那么我们下面用反正法证明一下。
假设 s≤7s\leq7 ,那么0≤ai≤7,i=1,…,60\leq a_i\leq7,i=1,\ldots,6 .
考虑到走7步刚好是绕一圈回到原点，不满足题意，所以步长不可能等于7.
又因为ai≠aja_i\neq a_j , i≠ji\neq j ,所以ai∈{1,2,3,4,5,6},i=1,…,6a_i\in\{1,2,3,4,5,6\},i=1,\ldots,6.
而1+2+3+4+5+6=211+2+3+4+5+6=21 ，是7的3倍，也就是说从标号0出发最后又回到了0点，这与题目要求的标号1-6点都到一次产生了矛盾。
故原假设不成立， s≥8s\geq8 。又因为，我们给出了一种 s=8s=8 的走法，所以 ss 的最小值就是8了。
上述两道竞赛题我们都是先给出了一个满足要求的解，然后利用反证法说明了大于或者小于这个值都不成立，于是说明我们给出的值是最优的解。
反证法的思想很简单，但是有时候推导矛盾还是蛮复杂的，并且竞赛方法众多，有时候我们是想不到用反证法做，所以平时可以多练练反证法找找感觉，培养一下技巧和意识。下面是 *** 中用反证法证明的例子，供大家练习：
1.证明有无限多个质数。
2.任意6人当中，求证或者有三人两两相识，或者有三人互不相识。
3.现有90张纸，每张纸都写有一个非负整数，已知这90个数之和小于1980，证明至少有三张数目相同的纸。
3. *** S={x:0
4.设n是大于1的整数，若所有小于或等于n\sqrt{n} 的质数都不能整除n，则n是质数。
5.已知三角形ABC是锐角三角形，且∠A>∠B>∠C。求证：∠B>45。
6.已知a、b为正实数，求证：a+b2≥ab\frac{a+b}{2} \geq \sqrt{a b} 。
7.已知a、b、c、d是实数，且ad-bc=1，求证：a2+b2+c2+d2+ab+cd≠1a^{2}+b^{2}+c^{2}+d^{2}+a b+c d \neq 1 。
8.一个群若同时是交换群和单群，则该群是循环群
9.若一个循环群是单群，则该群的阶为质数
10.若一个循环群的阶为质数，则该群为单群
11.鸽笼原理其中鸽笼原理我们之前也介绍过，有兴趣可以参看下文
双木止月Tong：【国际数学竞赛】鸽笼原理86 赞同 · 14 评论文章那么反证法的介绍就到这里吧，欢迎大家交流讨论~
对于国际数学竞赛及课程感兴趣的可参看：
双木止月Tong：【国际数学竞赛】目录98 赞同 · 2 评论文章