2012江苏省数学竞赛《提优教程》第69讲_无限递降与逐次调整

第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．则x30＝6x0y0z0－2y30－4z30，⑴由于x0，y0，z0为整数，故x0为偶数，设x0＝2x1，其中x1为正整数，又得8x31+2y30+4z30＝12x1y0z0，从而得y30＝6x1y0z0－2z30－4x31，⑵故y0也为偶数，设y0=2y1，其中y1为整数．于是又有2z30=12x1y1z0－4x31－8y31，故又有z0为偶数，设z0=2z1，其中z1为整数，代入即得x31+y31+z31=6x1y1z1．⑶从而(x1，y1，z1)也满足此方程，由于x1，y1，z1均是整数，且x1＞0，故(x1，y1，z1)也是方程的一组满足x1＞0的解．即(12x0，12y0，12z0)也是方程的满足12x0＞0的整数解．依此类推，可知(14x1，14y1，14z1)仍是方程的满足14x0＞0的整数解，由此(12nx0，12ny0，12nz0)(n∈N*)都是方程的满足12nx0＞0的整数解．但对于任何确定的正整数x0，12nx0不可能永远是正整数，从而方程没有使x0＞0的整数解，即原方程只有惟一组解(0，0，0)．说明本例所用的方法就是无限递降法，又称无限下推法．[来源:学科网]例2在m×n(m，n∈N*)的方格表的每个格子中都填入一个数．以后可以每次改变表中某一行或某一列的所有数的符号．证明：只要经过有限次的改变符号，就可以使每一行、每一列的各数之和都非负．分析这是一类操作题，是要证明经过有限次操作达到某个目标．我们可以为此目标设一上限(或下限)，从初始状态到此上限之间只有有限个中间状态，再证明每次操作都向此上限接近一步，从而此操作不能无限延续下去．解设第i行第j列填的数为aij(1≤i≤m，1≤j≤n，i，j∈N*)，且此方格表中所有各数的和为S＝1≤i≤m1≤j≤n∑aij．无论怎样改变其中每个格子中的数的符号(不改变此数的绝对值)，此和都是在和式1≤i≤m1≤j≤n∑(±aij)中适当选取每个数的符号的结果，从而只有有限个可能的和的值(显然该和至多有2mn种可能)，但所有这些和都不大于1≤i≤m1≤j≤n∑|aij|，即这些和有上限．如果填好后发现每行、每列的数的和都已经非负，则经过0次改变符号即已达到题目的要求．如果某一行(或列)的数的和为负，则可改变这一行(或列)的所有各数的符号．这时这一行(或列)中的数的和变大，而其余的行(或列)上的数不变，这样，操作一次就使这个表格中所有的数的和变大．由于可能的和式只有有限个值，故这种变大的过程不可能无限延续下去．必到某一时刻即无法再变大．此时，每一行、每一列的各数之和均非负．说明本例是无限递降的另一种叙述形式．在例1中说明了：只要有一组非零整数解，就一定有无穷多组整数解，这些解有递降(递升)关系；本例中每次操作的目标也存在递降(递升)关系，但是知道操作只有有限种可能的结果，因此经过有限次递降就必然得到满足要求的解答．这种形式更明白地说明了无限递降法与最小数原理的血缘关系．情景再现1．用无限递降法证明：2是无理数．2．试求方程x3－2y3－4z3=0的所有整数解．B类例题例311块铁，重量都是整数克，如果任意取其中10块，都可以把它们分成两组，每组5块铁，且这两组铁的重量相等．证明：这11块铁中的每块重量都相等．分析有的同学认为先任取10块，可以分成两组，若把把其中未取的一块与某组中的一块交换，两组重量相等，从而换入的一块与换出的一块重量相等，于是所有各块重量相等．这一想法为什么是错的？由于交换一块后，可以把此10块重新分组，因此不能说换出的一块与换入的一块重量相等．但是，这能说明，各块重量数的奇偶性相同．所以如果各块重量数为偶数，可以把每块重量数减半，而如果各块重量数为奇数，则可以把各块重量减去相同的重量，这样做不影响问题的结论．为此考虑减去谁能使问题得到简化？证明首先，满足条件的铁块具有以下三个性质：⑴这11块铁的重量数的奇偶性相同．这是因为，任何10块铁的和必须是偶数．否则分成重量相等的两组，每组的重量数就不是整数，但每组5块铁的重量数都是整数，其和应该是整数，二者矛盾．如A、B两块铁重量数的奇偶性不同，则当去掉A，用B与其余9块组成一组时其重量数的和为偶数，如用A换B，其余9块不变，则由于A、B的奇偶性不同，这个新的组的重量数的和就会是奇数了．⑵如果某11块铁满足题目要求，则将每块铁的重量都减去相同的某上重量后，仍能满足题目要求．⑶当各块铁的重量数都是偶数时，把每块铁的重量减半后，所得铁块仍然满足题目的要求．于是，若各块铁的重量数为奇数时，可都先减去一个奇数的重量，使各块铁的重量数变为偶数再减半．现在，设这些铁块的重量不全相等，则其中必有一块铁的重量最轻，设其重量数为m，把每块铁都减去m．则至少有一块铁的重量数为0．这时由⑴知，每块铁的重量数都是偶数．如果这时各块铁的重量数不全相同，则必有重量数不为0的铁块，把这些铁块的重量数记为2k×q的形式,其中k为正整数，q为奇数．在所有的k中，必有最小的一个k值，设此k值为k0．这时我们对这11块铁，连续减半k0次．则所得铁块仍能满足题目要求，但此时这11块铁的重量的奇偶性不同．（因为有铁块的重量数已经减成了奇数，但有的铁块重量数为0，是偶数）这与⑴产生矛盾．[来源:学科网]这说明，原来每块铁的重量都是m．例4证明方程x2+y2+z2=3xyz有无穷多组正整数解(x，y，z)．分析要说明方程有无穷多组正整数解，或者给出一个解的通式，满足此通式的数都是解，而此通式可以取无穷多组值．或者给出一个递推的方法，由此方法可以从一组解推出第二组解，这两种想法都是解决数列问题的常用想法．本题即是用第二种递推的想法，先找出易于发现的解，再寻找这些解的规律，由此得到寻找一般解的方法．证明若x＝y＝z＝a(a∈N*)，则3a2＝3a3，解得a＝1．即方程有解(1，1，1)；若x＝y＝1，则有2＋z2＝3z，得方程的另一组解(1，1，2)；若x＝1，y＝2，则有方程z2－6z＋5＝0，又得方程的另一组解(1，2，5)．现设(a0，b0，c0)(其中a0＜b0＜c0)是方程的一组正整数解，即a20＋b20＋c20＝3a0b0c0成立，考虑方程b20＋c20＋z2＝3b0c0z，即z2－3b0c0z＋(b20＋c20)＝0，此方程必有一正整数解z＝a0，由韦达定理，其另一解为z1＝3b0c0－a0必为正整数．于是原方程必有解(b0，c0，3b0c0－a0)且这一组解也满足b0＜c0＜3b0c0－a0．令a1＝b0，b1＝c0，c1＝3b0c0－a0为方程的一组满足a1＜b1＜c1的正整数解，则又可从此解出发得到方程的另一组解(b1，c1，3b1c1－a1)，这组解也满足b1＜c1＜3b1c1－a1，从而这组解与前面的解不同．这一过程可以无限延续下去，从而原方程有无穷多组解．例5在ABC中，求证：sinA+sinB+sinC≤332；分析可以猜到等号在A＝B＝C时相等，于是可以假设A、B、C不全相等，通过调整使三个正弦的和增大，从而原题可经逐次调整得证．证明若A≠B，则有sinA＋sinB＋sinC＝2sinA+B2cosA－B2＋sinC＜2sinA+B2＋sinC．即只要A、B、C中有任何两个不等，则可以通过上述方法对这三个角进行调整，使其正弦之和增大，从而只要这三个角不全相等，和sinA+sinB+sinC就不能取得最大值．故只有当A＝B＝C时此和取得最大值332．说明上述证明方法也是“逐次调整法”的一种表述形式，但这样的说法只是证明了“当三个角不等时，其正弦和不能取得最大值”，并没有证明原命题．因此这样的证明理由是不充足的．改进的证明为：若A、B、C不全相等，不妨设A≤B≤C，若B＜3，则取B＝3，C＝C＋B－3(3＜C＜C)．而sinC＋sinB－sinC－sinB＝2cosC+C2sinC－C2＋2cosπ3+B2sinπ3－B2(由C－C＝B－3)＝2sinπ3－B2(cosπ3+B2－cos2C＋B－π32)．由3＋B＜2C＋B－3，故sinC＋sinB－sinC－sinB＞0．[来源:学科网]即sinA+sinB+sinC＜sinA＋sinB＋sinC＝sinA＋sin3＋sin(23－A)＝2sin3cos(3－A)＋sin3＜3sin3＝332．对于B＞3，也可类似证明，若B＝3，则直接用上述证明的后半部分即可证．本题还可用添项法证明：证明2sinA+sinB+sinC+sin3＝2sinA+B2cosA－B2+2sin(6+C2)cos(6－C2)≤2sinA+B2+2sin(6+C2)＝4sin(A+B+C4+12)cos(A+B－C4－12)≤4sin3．从而sinA+sinB+sinC≤3sin3＝332．等号当且仅当A＝B＝C＝3时成立．本题还可用琴生不等式证明．例6设α为任一无理数，an={nα}({x}表示数x的“小数部分”，即记[x]为不超过x的最大整数，则{x}＝x－[x])，证明：存在无数个正整数n使an＞12．(南京大学强化班入学试题)分析本题似用反证法较合适．证明不妨设α＞0．设只有有限个整数n使an＞12，m是其中最大的一个，即对于任何t＞m，都有{tα}＜12．①取正整数t，使t＞m，令{tα}＝β，则据①，0＜β＜12．此时，2t＞m，于是由①，有{2tα}＜12，但由于0＜β＜12，故0＜2β＜1，所以{2tα}＝{2β}＝2β，于是由①知，0＜2β＜12．再取{22tα}，同理，由22tα＞m，得{22tα}＜12，又因0＜2β＜12，知0＜22β＜1，从而{22tα}={22β}=22β，又有0＜22β＜12，…，这一过程可以无限继续下去，于是得到0＜2nβ＜12(n∈N*)．这是不可能的，因只要β≠0，就必存在正整数k，使2－kβ2－k+1，此时有2k－1β＞12．命题得证．说明本题实际上说明了，无理数{nα}(n取全体正整数)时在区间(0．1)上是处处“稠密”的．情景再现3、证明方程6(x2+y2)=z2+t2无正整数解．4．若干个球装在2n+1个口袋中，如果任意取走1袋，总可以把余下的2n袋分成两组，每组n袋，并且这两组的球的个数相等．证明：每个袋中的球的个数都相等．(90年意大利数学竞赛)C类例题例7正五边形的每个顶点对应着一个整数，使得这五个数的和为