当前位置:首页 >> >>

江苏省数学竞赛《提优教程》教案 第69讲 无限递降与逐次调整 Word版 含答案

第 69 讲 无限递降与逐次调整 无限递降法是一种常用的证明方法,首先由费马(Fermat)使用,数学竞赛也有较广泛的 应用.与之相似的逐次调整法也是证明很多问题的重要方法. 无限递降法的理论根据是最小数原理: 命题一 有限个实数中,必有一个最小数(也必有一个最大数). 根据这一原理,又可得出: 命题二 任意有限个两两不同的实数可以从小到大排列顺序.(排序原理) 对于自然数集,有 最小数原理 若 M 是正整数数集 N*的任一非空子集(有限或无限均可),则 M 中必有最小 的数. 最小数原理常用于论证存在性命题.在解题时,也常用由最小数原理演化出的最优化原 则(极端原理). A 类例题 例 1 求方程 x3+2y3+4z3=6xyz 的所有整数解(莫斯科中学生竞赛). 分析 要求此方程的所有整数解,但这个方程的解的情况我们并不清楚,但其解的情况不 外以下几种: 1? 方程没有整数解:对这种情况,我们必须证明一切整数都不是这个方程的解; 2? 方程只有有限组解:对这种情况,我们必须把所有的解都求出来,并证明方程没有别 的解; 3? 方程有无数组解:对这种情况,我们应给出如何找到这无数组解中的任一组解的方法, 并证明没有其他类型的解了. 情形 1?是很容易否定的,因为我们可以发现 x=y=z=0 就是方程的一组解.那么方程还 有没有其他的解呢?一时找不到其他的解,那么,是否只有这一组解呢?不妨设方程还有一 组解,试着推出这组解的特点.从而确定方程的所有的解. 解 显然 x=y=z=0 是方程的一组解. 如果方程有一组解(x,y,z),则必有一组解(-x,-y,-z),故只要考虑方程的正整数 解即可. 设(x0,y0,z0)是方程的一组解,其中 x0>0.则 x0=6x0y0z0-2y0-4z0, ⑴ 由于 x0,y0,z0 为整数,故 x0 为偶数,设 x0=2x1,其中 x1 为正整数,又得 3 +4z0=12x1y0z0, 从而得 y0=6x1y0z0-2z0-4x1, 故 y0 也为偶数,设 y0=2y1,其中 y1 为整数.于是又有 2z0=12x1y1z0-4x1-8y1, 故又有 z0 为偶数,设 z0=2z1,其中 z1 为整数,代入即得 x1+y1+z1=6x1y1z1. ⑶ 从而(x1,y1,z1)也满足此方程,由于 x1,y1,z1 均是整数,且 x1>0,故(x1,y1,z1)也 1 1 1 1 是方程的一组满足 x1>0 的解.即(2x0,2y0,2z0)也是方程的满足2x0>0 的整数解.依此类 1 1 1 1 1 1 1 推,可知(4x1,4y1,4z1)仍是方程的满足4x0>0 的整数解,由此(2nx0,2ny0,2nz0)(n∈N*)都 3 3 3 3 3 3 3 3 3 3 3 3 8x1+2y0 3 3 ⑵ 1 是方程的满足 nx0>0 的整数解. 2 1 但对于任何确定的正整数 x0,2nx0 不可能永远是正整数,从而方程没有使 x0>0 的整数 解,即原方程只有 惟一组解(0,0,0). 说明 本例所用的方法就是无限递降法,又称无限下推法. [来源:www.shulihua.net] 例 2 在 m×n(m,n∈N*)的方格表的每个格子中都填入一个数.以后可以每次改变表中某 一行或某一列的所有数的符号.证明:只要经过有限次的改变符号,就可以使每一行、每一 列的各数之和都非负. 分析 这是一类操作题,是要证明经过有限次操作达到某个目标.我们可以为此目标设一 上限(或下限),从初始状态到此上限之间只有有限个中间状态,再证明每次操作都向此上限接 近一步,从而此操作不能无限延续下去. 解 设第 i 行第 j 列填的数为 aij(1?i?m,1?j?n,i,j∈N*),且此方格表中所有各数的 和为 S= ∑ aij. 1?i?m 1?j?n 无论怎样改变其中每个格子中的数的符号(不改变此数的绝对值),此和都是在和式 ∑ 1?i?m 1?j?n (±aij)中适当选取每个数的符号的结果, 从而只有有限个可能的和的值(显然该和至多有 2mn 种 可能),但所有这些和都不大于 ∑ |aij|,即这些和有上限. 1?i?m 1?j?n 如果填好后发现每行、每列的数的和都已经非负,则经过 0 次改变符号即已达到题目的 要求. 如果某一行(或列)的数的和为负,则可改变这一行(或列)的所有各数的符号.这时这一行 (或列)中的数的和变大,而其余的行(或列)上的数不变,这样,操作一次就使这个表格中所有 的数的和变大. 由于可能的和式只有有限个值,故这种变大的过程不可能无限延续下去.必到某一时刻 即无法再变大.此时,每一 行、每一列的各数之和均非负. 说明 本例是无限递降的另一种叙述形式.在例 1 中说明了:只要有一组非零整数解,就 一定有无穷多组整数解, 这些解有递降(递升)关系; 本例中每次操作的目标也存在递降(递升) 关系,但是知道操作只有有限种可能的结果,因此经过有限次递降就必然得到满足要求的解 答.这种形式更明白地说明了无限递降法与最小数原理的血缘关系. 情景再现 1.用无限递降 法证明: 2是无理数. 2.试求方程 x3-2y3-4z3=0 的所有整数解. B 类例题 例 3 11 块铁,重量都是整数克,如果任意取其中 10 块,都可以把它们分成两组,每组 5 块铁,且这两组铁的重量相等.证明:这 11 块铁中的每块重量都相等. 分析 有的同学认为先任取 10 块,可以分成两组,若把把其中未取的一块与某组中的一 块交换,两组重量相等,从而换入的一块与换出的一块重量相等,于是所有各块重量相等.这 一想法为什么是错的?由于交换一块后,可以把此 10 块重新分组,因此不能说换出的一块与 换入的一块重量相等. 但是,这能说明,各块重量数的奇偶性相同.所以如果各块重量数为偶数,可以把每块 重量数减半,而如果各块重量数为奇数,则可以把各块重量减去相同的重量,这样做不影响

更多相关标签: