当前位置:首页 >> 学科竞赛 >>

2012江苏省数学竞赛《提优教程》教案:第9讲


第 9 讲 无限递降与逐次调整
无限递降法是一种常用的证明方法,首先由费马(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). 说明 本例所用的方法就是无限递降法,又称无限下推法. 例 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 块重新分组,因此不能说换出的一块与

换入的一块重量相等. 但是,这能说明,各块重量数的奇偶性相同.所以如果各块重量数为偶数,可以把每块 重量数减半,而如果各块重量数为奇数,则可以把各块重量减去相同的重量,这样做不影响 问题的结论.为此考虑减去谁能使问题得到简化? 证明 首先,满足条件的铁块具有以下三个性质: ⑴这 11 块铁的重量数的奇偶性相同.这是因为,任何 10 块铁的和必须是偶数.否则分 成重量相等的两组,每组的重量数就不是整数,但每组 5 块铁的重量数都是整数,其和应该 是整数,二者矛盾.如 A、B 两块铁重量数的奇偶性不同,则当去掉 A,用 B 与其余 9 块组成 一组时其重量数的和为偶数,如用 A 换 B,其余 9 块不变,则由于 A、B 的奇偶性不同,这个 新的组的重量数的和就会是奇数了. ⑵ 如果某 11 块铁满足题目要求,则将每块铁的重量都减去相同的某上重量后,仍能满 足题目要求. ⑶ 当各块铁的重量数都是偶数时,把每块铁的重量减半后,所得铁块仍然满足题目的要 求. 于是,若各块铁的重量数为奇数时,可都先减去一个奇数的重量,使各块铁的重量数变 为偶数再减半. 现在,设这些铁块的重量不全相等,则其中必有一块铁的重量最轻,设其重量数为 m, 把每块铁都减去 m. 则至少有一块铁的重量数为 0. 这时由⑴知, 每块铁的重量数都是偶数. 如 k 果这时各块铁的重量数不全相同, 则必有重量数不为 0 的铁块, 把这些铁块的重量数记为 2 ×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, 0, 0) (其中 a0<b0<c0)是方程的一组正整数解, a0+b0+c0=3a0b0c0 成立, b c 即 2 2 2 考虑方程 b0+c0+z =3b0c0z,即 2 2 z2-3b0c0z+(b0+c0)=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,从而 这组解与前面的解不同. 这一过程可以无限延续下去,从而原方程有无穷多组解. 3 3 例 5 在 ? ABC 中,求证:sinA+sinB+sinC? ; 2
2 2 2

分析 可以猜到等号在 A=B=C 时相等,于是可以假设 A、B、C 不全相等,通过调整使 三个正弦的和增大,从而原题可经逐次调整得证. A-B A+B A+B 证明 若 A≠B,则有 sinA+sinB+sinC=2sin cos +sinC<2sin +sinC. 2 2 2 即只要 A、B、C 中有任何两个不等,则可以通过上述方法对这三个角进行调整,使其正 弦之和增大,从而只要这三个角不全相等,和 sinA+sinB+sinC 就不能取得最大值. 3 3 故只有当 A=B=C 时此和取得最大值 2 . 说明 上述证明方法也是“逐次调整法”的一种表述形式,但这样的说法只是证明了“当 三个角不等时,其正弦和不能取得最大值” ,并没有证明原命题.因此这样的证明理由是不充 足的.改进的证明为: 若 A、B、C 不全相等,不妨设 A?B?C,若 B< ,则取 B?= ,C?=C+B- ( <C?< 3 3 33 C). π π 3 +B 3 -B C?+C C?-C ? 而 sinC?+sinB?-sinC-sinB=2cos sin +2cos sin (由 C?-C=B- ) 2 2 2 2 3 π π π -B +B 2C+B- 3 3 3 =2sin 2 (cos 2 -cos ). 2 由 +B<2C+B- ,故 sinC?+sinB?-sinC-sinB>0. 3 3 即 sinA+sinB+sinC<sinA+sin B?+sinC? 2? ? =sinA+sin3+sin( 3 -A)

?

?

??

?

?

? ? ? ? 3 3 =2sin3cos(3-A)+sin3<3sin3= 2 .
对于 B>3,也可类似证明,若 B=3,则直接用上述证明的后半部分即可证. 本题还可用添项法证明: 证明 2 sinA+sinB+sinC+sin3 A-B A+B ? C ? C =2sin 2 cos 2 +2sin(6+ 2 )cos(6- 2 ) A+B ? C ?2sin +2sin( + ) 2 6 2 A+B-C ? A+B+C ? ? =4sin( 4 +12)cos( -12)?4sin3. 4

?

?

?

? 3 3 ? 从而 sinA+sinB+sinC?3sin3= 2 .等号当且仅当 A=B=C=3时成立.
本题还可用琴生不等式证明. 例 6 设 α 为任一无理数,an={nα}({x}表示数 x 的“小数部分” ,即记[x]为不超过 x 的最大

1 整数,则{x}=x-[x]),证明:存在无数个正整数 n 使 an> .(南京大学强化班入学试题) 2 分析 本题似用反证法较合适. 1 证明 不妨设 α>0.设只有有限个整数 n 使 an>2,m 是其中最大的一个, 即对于任何 t>m,都有 1 {tα}< . 2 ①

1 取正整数 t,使 t>m,令{tα}=β,则据①,0<β<2. 1 此时,2t>m,于是由①,有{2tα}< , 2 1 1 但由于 0<β< ,故 0<2β<1,所以{2tα}={2β}=2β,于是 由①知,0<2β< . 2 2 1 1 再取{22tα},同理,由 22tα>m ,得{22tα}< ,又因 0<2β< ,知 0<22β<1, 2 2 1 从而{22tα}={22β}=22β,又有 0<22β< ,?, 2 1 这一过程可以无限继续下去,于是得到 0<2 nβ< (n∈N*). 2 这是不可能的,因只要 β≠0,就必存在正整数 k,使 2 k<β<2
- -k+1

1 - ,此时有 2k 1β> . 2

命题得证. 说明 本题实际上说明了,无理数{nα}(n 取全体正整数)时在区间(0.1)上是处处“稠密” 的.

情景再现
3、证明方程 6(x2+y2)=z2+t2 无正整数解. 4.若干个球装在 2n+1 个口袋中,如果任意取走 1 袋,总可以把余下的 2n 袋分成两组, 每组 n 袋,并且这两组的球的个数相等.证明:每个袋中的球的个数都相等.(90 年意大利数 学竞赛)

C 类例题
例 7 正五边形的每个顶点对应着一个整数,使得这五个数的和为正.若其中 3 个相连顶 点对应的整数依次为 x、y、z,且 y<0,则要进行如下的操作:把整数 x、y、z 分别换为 x+y, -y,z+y,这算一次操作.只要所得五个整数中至少有一个整数为负数时,操作就要继续进 行.问这种操作是否经过有限次后就一定能终止.(27 届 IMO) 分析 选定一个目标函数,证明每次操作目标函数值向某方向进一步,但又只能有有限种 取值可能. 解 1 不妨设某次五个顶点上的数分别为 x1,x2,x3,x4,x5,且 S= x1+x2+x3+x4+x5>0.又 设 x1<0,进行一次操作后的五个数为-x1,x1+x2,x3,x4,x1+x5,此时 S 保持不变. 取函数 f(x1,x2,x3,x4,x5)=(x1-x3)2+(x2-x4)2+(x3-x5)2+(x4-x1)2+(x5-x2)2,显然 f ?0 则 f(-x1,x1+x2,x3,x4,x1+x5)-f(x1,x2,x3,x4,x5)=2x1(x1+x2+x3+x4+x5)?-2.

这说明, 每操作一次 f 的值至少减少 2, f 恒?0, 但 故这样的操作经过有限次就一定终止. 解 2 取目标函数 f(x1,x2,x3,x4,x5) =|x1|+|x2|+|x3|+|x4|+|x5|+|x1+x2|+|x2+x3|+|x3+x4|+|x4+x5|+|x5+x1| +|x1+x2+x3|+|x2+x3+x4|+|x3+x4+x5|+|x4+x5+x1|+|x5+x1+x2|+|x1+x2+x3+x4| +|x2+x3+x4+x5|+|x3+x4+x5+x1|+|x4+x5+x1+x2|+|x5+x1+x2+x3|+|x1+x2+x3+x4+x5|. 显然 f(x1,x2,x3,x4,x5)?0. 则 f( - x1 , x2+x3 , x3 , x4 , x5+x1) - f(x1 , x2 , x3 , x4 , x5)= |x1+x2+x3+x4+x5+x1| - |x2+x3+x4+x5|=|s+x1|-|s-x1|. (记 s=x1+x2+x3+x4+x5 由于 s>0,x1<0,故|s+x1|-|s-x1| <0.下同解 1. 例 8 设 a 是给定的正整数,A、B 是两个实数,试确定方程组 ⑴ ? ? x +y +z =(13a) , 1 ? 2 2 2 2 2 2 2 2 2 4 ? ?x (Ax +By )+y (Ay +Bz )+z (Az +Bx )=4(2A+B)(13a) . ⑵ 有正整数解的充分必要条件(用 A、B 的关系式表示,并予以证明)(第五届全国冬令营) 1 解 ⑵即 A(x4+y4+z4)+B(x2y2+y2z2+z2x2)= (2A+B)(13a)4.故消去(x2y2+y2z2+z2x2)项: 4 1 1 1 1 ⑵-⑴2× B:(A- B)(x4+y4+z4)= (A- B)(13a)4. 2 2 2 2 如果 2A-B≠0,则得, 2(x4+y4+z4)=(13a)4. ⑶如果有正整数解,设为(x0,y0,z0),
4 4 4

2

2

2

2



显然 a 为偶数,令 a=2a1,则 x0+y0+z0=8(13a1)4. 由于奇数的 4 次方被 8 除余 1,偶数的 4 次方被 8 除余 0,故 x0,y0,z0 都是偶数. 令 x0=2x1,y0=2y1,z0=2z1,于是得 2(x1+y1+z1)=(13a1)4.即(x1,y1,z1)也是正整数解. 1 由此可知, 这个方程有无数组解. 且对于一切正整数 n, nx0 都是正整数. 这是不可能的. 于 2 是 2A-B≠0 时方程⑶无正整数解. 当 2A-B=0 时,无论 A=0 或 A≠0,均有解 x=3a,y=4a,z=12a. 即所求充要条件为 2A-B=0.
4 4 4

情景再现
5.一群小孩围坐一圈分糖果,老师让他们先每人任取偶数块糖,然后按下列方法调整: 所有小孩同时把自己手中的糖分一半给左边的小孩,糖块数变成奇数的小孩向老师要 1 块, 这算一次调整.证明:经过有限次调整后,大家的糖块数就变得一样多了.(1962 年北京市高 中数学竞赛) 6.把 1979 分成若干个正整数的和,要使分成各数的乘积最大,应如何分? x 7.已知对任意实数 x,函数 f(x)都有定义,且 f 2(x)?2x2f (2).如果集合 A={a|f(a)>a2} 不是空集,试证 A 是无限集.(1994 年江苏省数学竞赛) 8.空间有 1989 个点,其中无三点共线,把它们分成点数互不相同的 30 组,取任意三个 不同组的点为顶点作三角形,问各组点数应为多少时,才能使所得三角形总数最多?

习题 69
1.证明:四元二次不定方程 x2+y2=3(u2+v2) 不存在正整数解. 2.确定(并证明)方程 a2+b2+c2=a2b2 的所有整数解.(美国第五届数学竞赛) 3、已知 f(x)是定义在 N*上又在 N*上取值的单调递增函数,且对于任何 m∈N*,有 m f(2 )=2m,证明 f(x)=x 在 N*上恒成立. 4.若 x1,x2,?,xn 为非负数,且 x1+x2+?+xn=π,(n?2) 试求 sinx1+sinx2+?+sinxn 的最大值.(1987 年南京市竞赛) . 5.试证明排序不等式:设 ai?ai+1,bi?bi+1,(i=1,2,?,n-1).则∑aibi?∑aibj ?
i=1 i=1
i

n

n

∑aibn+1
i=1

n

-i

.( j1,j2,?,jn 是 1,2,?,n 的一个排列).

a1 a2 an 1 6.用逐次调整法证明:设 a1, a2,?,an 是互不相等的正整数,求证: 2+ 2+?+ 2?1+ 1 2 n 2 1 1 + +?+ ;(第二十届 IMO) 3 n 7.用逐次调整法说明:在给定圆的内接三角形中,求面积最大的三角形. 8.用逐次调整法说明:锐角三角形的内接三角形中,以三高的垂足为顶点的三角形的周 长最小. 9.有无数个长与宽都是正整数的矩形 S1,S2,?,Sn,?.其中 Si 的顶点为(0,0),(ai, 0),(ai,bi),(0,bi)(ai,bi∈N*,i=1,2,?.).求证:可从中选出无穷多个矩形排成一个矩 形序列,使前一个矩形在后一个矩形之内. 10.在坐标平面上,如果 x0、y0 都是整数,则把点(x0,y0)称为整点(或格点).试证明: 不存在正 n(n?7)边形,其所有顶点都是整点. 11.三个箱子装了一些小球,每个箱子都有足够大,可以进行如下操作:从任一箱子中 拿出与另一个箱子中数目相等的小球放入后者. 证明:不论最初三个箱子中各有多少个小球,总可以经过有限次操作,使其中某个箱子 变成空的. 12.亚瑟王(传说中的英国国王)在王宫中召见他的 2n 名骑士,其中某些骑士之间互相有 仇,已知每个骑士的仇人不超过 n-1 个,证明:摩尔林(亚瑟王的谋士)能够让这些骑士围着 圆桌坐下,使每个骑士都不与他的仇人相邻.(本题也可用以下方式叙述: G 为简单图,顶点 数 n?3,且对每个不相邻的顶点 V 与 V?,它们的次数和都?n,那么,G 有哈密尔顿圈.)

本节“情景再现”解答:

r 1.证明:设 2为有理数, 2= (r、s∈N*),则 2s2=r2.故 r 为偶数.设 r=2r1(r1∈N*). s 代入就有 s2=2r12,又得 s 为偶数.再设 s=2s1,则得 2s1=r1. 重复上一步骤,可依次得一列无限多个正整数 r,r1,r2,?,rn,?,其中 rk=2rk+1(k∈ N*). 且 r>r1>r2>?>rn>?,但小于 r 的正整数只有有限的 r-1 个,二者矛盾.故证. 2.解:方程显然有一解:x=y=z=0.若(x,y,z)是一组解,则(-x,-y,-z)也是一组 解.故只要考虑 x>0 的解即可. 设 S 是所有 x>0 的整数解的集合.取其中使 x 的值最小的一组(x1,y1,z1)(x1,y1,z1 ∈Z). 则 x1-2y1-4z1=0. 即 x1=2y1+4z1. 3 3 3 3 3 由于 2y1+4z1为偶数,故 x1 为偶数,设 x1=2x2(x2∈N*),代入得:8x2=2y1+4z1. 3 3 3 3 3 3 约去 2 得, 1=4x2-2z1, y 于是又得 y1 为偶数. y1=2y2(y2∈Z), 令 代入又得 8y2=4x2-2z1, 3 3 3 即 z1=2x2-4y2,又得 z1 为偶数,令 z1=2z2(z2∈Z) 3 3 3 就得 x2-2y2-4z2=0.这说明(x2,y2,z2)也是原方程的一组解, x2>0,故 x2<x1.这 但 与 x1 的最小性矛盾.故方程不能有使 x>0 的解.即 x=y=z=0 是方程的唯一解. 3.证明:设方程有正整数解,其中(x,y,z,t)是使 x 最小的一组解,则 3|(z2+t2) 若 z≡0(mod 3)或 t≡0(mod 3),则 z2+t2≡0(mod 3).于是 z≡0,t≡0(mod 3). / / / 2 2 2 令 z=3z1,t=3t1,代入得,2(x +y )=3(z1 +t12).于是又有 x≡0,y≡0(mod 3). 令 x=3x1,y=3y1,代入又得 6(x12+y12)=z12+t12.这说明(x1,y1,z1,t1)也是方程的解.而 且 x1<x.与 x 的最小性矛盾.故证. 4.证明 ⑴ 所有的袋中球数的奇偶性相同. ⑵ 把每个袋中的球数都减少同一个数目,不影响结论的正确性; ⑶ 如果每个口袋中的球数有公因子 d,则把这个公因子约去,不影响结论的正确性. 由此,设各口袋中球数不全相等,取各袋球数最少的,设为 k. ⑴先把每个口袋中的球数减 k,于是,至少有一个口袋中球数为 0,而其余各袋中球数为 偶数. ⑵把各袋中的球数都减半,此时由于有一袋中球数为 0,故这一袋中球数仍为偶数.于是 其余各袋中球数都仍为偶数. ⑶于是,可以再把各袋中球数减半,而同理知此时各袋中球数仍全为偶数.这一过程可 以无限继续下去,这是不可能的.即得证. 5.证明 设调整开始前,拿糖块最多的小孩拿了 2m 块糖,最少的拿了 2n 块糖(n,m∈ N*,0?n?m). 若 n=m,则所有小孩拿糖块数已经相等,不再需要调整.现设 n<m.下面证明: 引理 1° 经过一次调整后,每个小孩的糖块还在 2n 与 2m 之间; 设某小孩手中有糖 2k 块,他左边的小孩有 2l 块(k,l∈N*,且 n?k,l?m),经过一次调 整,他手中的糖变为(当 k+l 为偶数时) k+l 块或(当 k+l 为奇数时)k+l+1 块. 因 n?k,l?m,故 2n?k+l?2m. 当且仅当 k=l=n 时,k+l=2n 成立;当且仅当 k=l=m 或 k=m,l=m-1 或 k=m-1,l=m 时, 有 k+l=2m,或 k+l+1=2m. 故经过一次调整,所有小孩手中的糖块数还在 2n 与 2m 之间. 引理 2° 经过一次调整后,只要 n<m,手上有 2n 块糖的小孩人数就至少减少 1 人. 首先,调整前手中糖块数多于 2n 的小孩,经调整后,手中糖数仍多于 2n. 若调整前某小孩手中有 2k 块糖(k>n), 他左边的小孩有 2l 块糖, l?n, 但 所以 k+l>2n. 从
3 3 3 3 3 3 2 2

而这个小孩手中的糖数(k+l 或 k+l+1)多于 2n. 其次,调整前手中有 2n 块糖的小孩人数至少减少 1 人. 调整前手中有 2n 块糖的小孩,当且仅当其左边小孩手中也是 2n 块时,调整后手中仍为 2n 块.但只要 n<m,就至少有一名手中有 2n 块糖的小孩,其左边小孩的糖多于 2n 块.于 是经过调整,这名手中有 2n 块糖的小孩手中的糖数就多于 2n 块了,故经过一次调整,手中 有 2n 块糖的小孩至少减少 1 人. 由 1?与 2?知,若原来手中有 2n 块糖的小孩共有 h(h∈N*)人,经过至多 h 次调整后,每个 小孩手中的糖数都不多于 2m,不少于 2n+2. 如果 2n+2<2m,再经过有限次调整后,每个小孩手中的糖块数又会不多于 2m 而不少于 2n+4.??. 由于 n,m 都是正整数,n 与 m 之间的整数只有有限个,所以,经过有限次调整后,每个 小孩手中的糖数都变得一样多. 6.考虑一般情况:对于任意正整数 n,如果 n 分拆成的某数 a?5,则把它拆成 3 与 a-3, 由于 3(a-3)=3a-9=a+(2a-9)>a,故所得分拆使其积变大.如果最后最后拆成的数中所 有数都?4,当 4 的个数?2 时,把 4+4 改成 3+3+2,则 4×4<3×3×2.当只有 1 个 4 时,把 4 改成 2+2,而当 2 的个数?3 时,把 2+2+2 改成 3+3,则 2×2×2<3×3.于是 可知,如果原数被 3 整除,则把它全部拆成 3 的和;如果原数被 3 除余 1,则拆成 2 个 2,其 余全部是 3 的和;原数被 3 除余 2,则拆出 1 个 2,其余全部为 3 的和.这样可使积最大.对 于 n=1979≡2(mod 3).故只要拆成一个 2 与 659 个 3 的和,此时其积 2×3659 最大. 0 7.解 由于 f 2(0)?2· 2· ( ),即 f(0)=0.即 0?A. 0 f 2 设 a∈A,显然 a≠0,又由 a∈A,知 由 f(x)定义,有 比较①、②,有 f(a)>a2, ① ② a f 2(a)?2a2f ( ), 2 a f2(a) a2 a f ( )? 2 > >( )2. 2 2a 2 2

a a a 于是2∈A.但由 a≠0,故2≠a,即2与 a 是 A 的(相异的)两个元素. a a a a a a a 同理,由 ∈A, ≠0,又可得 ∈A.由此可知,a, , 2, 3,?, n,?(n∈N)都是 2 2 4 2 2 2 2 A 的元素,即 A 为无限集. 8.设分成各组的点数分别为 n1,n2,?,n30,且 n1<n2<?<n30,n1+n2+?+n30= 1989.则可得三角形总数 S= 现固定 n3,?,n30.则 S=n1n2 ∑ nk+(n1+n2)
k=1 30



1?i<j<k?30

ninjnk.



3?j<k?30

njnk+



3?i<j<k?30

ninjnk.

故要使 S 最大,n2-n1 应尽可能小,故 n2-n1=1 或 2.同法可知应有 ni+1-ni=1 或 2, 且至多有 1 组相邻两数差为 2. 由于若所有相邻两数差为 1 时, 30 个数的和为 15 的倍数, 1989 不是 15 的倍数. 此 而 故 设此 30 组的点数为 n,n+1,?n+k-1,n+k+1,?,n+30.于是前 k 个数都加 1 后, 30 个数的和=1989+k, 15|1989+k?k=6. 且 2n+31=133?n=51. 即分成数为 51, ?, 52, 56,58,59,?,81.

“习题 69”解答: 1.证明 设方程有正整数解.不妨设(x0,y0,u0,v0)是其中使 x2+y2 最小的一组解. 由于左边能被 3 整除,若 3?x,或 3?y,则 x2+y2≡1 或 2(mod 3),故 x≡0(mod 3),y≡ 0(mod 3). 设 x=3x1,y=3y1,代入得 u0+v0=3(x12+y12),这说明(u0,v0,x1,y1)也是原方程的一组解, 2 2 2 但 u +v0<x0+y0,即得到的一组解使 x2+y2 更小.这与假设矛盾.故原方程没有正整数解. 2.解 a=b=c=0 是一组解.设(a0,b0,c0)是一组非零解. ⑴ a、b、c 不能都是奇数,否则左边被 4 除余 3,右边被 4 除余 1,矛盾. ⑵ a,b,c 不能二奇一偶,否则左边被 4 除余 2,右边被 4 除余 0 或 1,矛盾; ⑶ a,b,c 不能一奇二偶,否则左边被 4 除余 1,右边被 4 除余 0,矛盾; ⑷ a,b,c 都是偶数,则约去左、右两边所有的公因子 2 后,必得上述三者之一. 从而本题只有唯一解. 3.证明:1?f(1)<f(2)=2,故 f(1)=1,f(2k)=2k,f(2k+1)=2k+1, 而 2k=f(2k)<f(2k+1)<f(2k+2)<?<f(2k+1-1)<f(2k+1)=2k+1. 由于在 2k<x<2k+1 的自然数共有 2k-1 个:2k+1,2k+2,?,2k+1-1. 而 f(2k)、f(2k+1)、f(2k+2)、?、f(2k+1-1)这 2k-1 个互不相等的函数值也只有取这 2k-1 个值. 即得 f(x)=x 在 2k<x<2k+1 上恒成立. k 可取一切正整数, 由 故得对于一切 x∈N*, f(x)=x 成立. 4.分析:可先讨论 n=2,3 的情况,再推广到一般情况. 解:令 Sn=sinx1+sinx2+sinx3+?+sinxn
2 1 2 2

当 n=2 时,S2=sinx1+sinx2?1+1=2,当且仅当 x1=x2=

?
2

时等号成立;

当 n=3 时,S3=sinx1+sinx2+sinx3= sinx1+sinx2+sin(x1+x2) =2sin x1-x2 x1+x2 cos 2 +sin(x1+x2) 2

x1+x2 x1+x2 x1+x2 ?2sin 2 +2sin 2 cos 2 x1+x2 =2sin2?(1+cos2?)=8sin?cos3?.其中 2?= . 2 所以 S32=82sin2?cos6?= 故 3 3 S3? 2 64 64 3 33 · 2?· 2?· 2?· 2?? · )4= . 3sin cos cos cos ( 3 3 4 4 .当且仅当 x1=x2=x3= 3 时取最大值.

?

猜测,x1=x2=?=xn= 时 Sn 取最大值 nsin .下面证明这个结论: n n 若 x1、x2、?、xn 不全相等,则必有某个 xi< ,也有某个 xj> .就设 x1< ,x2> . n n n n x1-x2 x1+x2 x1+x2 ? ? ? 则 sinn+sin(x1+x2-n)-(sinx1+sinx2)=2sin 2 (cos ( 2 -n)-cos 2 ) x1- -x2 n n x1+x2 =2sin 2 ·2sin 2 sin 2 >0.

?

?

?

?

?

?

?

?

即把 x1 换成 ,x2 换成 x1+x2- ,其余的角保持不变后,和增大,若还有不等于 的角, n n n 则仍可继续这个过程, 至多替换 n-1 次, 就可使每个角都等于n, 此时已无法使 Sn 再增大. 故 得最大值为 nsinn. 又证:由琴生不等式,即有 Sn=sinx1+sinx2+sinx3+?+sinxn ?nsin nsinn. 5.证明:用逐次调整法证明如下: 若 j1≠1,jk=1(k>1),因 a1b1-a1bj1-akbjk+akbj1=(a1-ak)(b1-bj1)?0, x1+x2+x3+?+xn = n

?

?

?

?

?

?

∑aibj =a1bj +a2bj +?+akbj +?+anbj
i=1
i 1 2 k

n

n

?(a1b1-a1bj1-akbjk+akbj1)+a1bj1+a2bj2+?+akbjk+?+anbjn =a1b1+a2bj2+?+akbj1+?+anbjn. 即经过一次调整,使和式中的第 1 项 a1bj1及第 k 项 akb1 分别换成 a1b1 及 akbj1,其余各项 都没有改变,经过这样变化,其和不减.若 j1=1,则此步调整可以不做,直接考虑下一步. 此时,若 j2≠2,又可用同样的方法调整,使和式的第 2 项变成 a2b2,而和不减;??, 这样经过至多 n-1 次调整,就可使和式变为∑aibi,且每次调整时其和都不减从而左边的不
i=1

n

等式得证.同法可证右边的不等式. 6.证明:设 a1,a2,?,an 按大小排列为 aj1<aj2<?<ajn, a 1 a k a j1 a 1 1 1 若 j1=k,1<k?n,则12+k2-(12 +k2 )=(a1-ak)(12-k2)?0. a j1 a1 a2 an a1 ak a1 于是,在和式 2+ 2+?+ 2中,把 2换成 2 ,把 2换成 2 ,其余各项不动,则其和不增, 1 2 n 1 1 k k 即 a1 a2 ak a n a j1 a 2 a1 an 12+22+?+k2+?+n2?12 +22+?+k2 +?+n2;(若 j1=1,则此步调整可以不做,直接 考虑下一步) a j2 a2 ak? a2 若 j2=k?≠2,则又可把22换成22 ,而把 2换成 2,其余各项不动,仍可证明,经过这样 k? k? a j1 a j2 a jn 的交换, 其和不增, ??, 这样经过至多 n-1 次调整, 使和式换成12 +22 +?+n2 , 而和不增. 即 a jn a1 a2 a n a j1 a j2 + +?+ 2? 2+ 2 +?+ 2 . 12 22 n 1 2 n ①

a jk k 1 但 aj1<aj2<?<ajn,故 aj1?1,aj2?2,?,ajn?n,从而k2 ?k2=k (k=1,2,?,n), 故又得, a j1 a j2 a jn 1 1 1 2 + 2 +?+ 2 ?1+ + +?+ . 1 2 n 2 3 n ②

比较①、②,得证. 7.证明:设⊙O 为给定圆,△ABC 为其内接三 角 形 , 若 AB ≠ A' A AC,则作 BC 边上的高 AD 及 BC 的垂直平分线 A?M 交 BC 于点 M,交 ⊙O 于点 A?,显然 A?M>AD.于是 S△A?BC>S△ABC, 这说明,只要定⊙ O 的内接三角形的两边不等,就可调整此三角形使其 面积增大,故此三 O 角形不是圆的内接三角形中面积最大的,从而,当圆 的内接三角形三 M D C B 边相等时,其面积才不能再增大,即圆的内接三角形 中面积最大的为 正三角形. 8. 解: 设△DEF 是△ABC 的任一内接三角形 (D、 F 分别在边 E、 A BC、CA、AB 上),若∠FDB≠∠EDC,则作点 F 关于 BC 的对称点 F?,连 F?E 交 BC 于点 D?,连 ED?、FD?,显然, FD’ + D?E < FD + F E DE.这说明,只要内接三角形的某两边与原三角 形的相应边夹角不 等,则可通过上法调整此三角形,使其周长变小, 故此三角形不是内 B C D D' 接三角形中周长最小的. 故只有当内接三角形的任 两边与相应边的夹 角都相等时,其周长才不能再减小.即此时得到的 三角形是其内接三 F' 角形中周长最小的. 而当内接三角形的任两边与相应边的夹角都相等时,此三角形是以原三角形的高的垂足 为顶点的三角形.故以三高的垂足为顶点的三角形是三角形的内接三角形中周长最小的. 9.证明 把题中的矩形简记为(ai,bi).即用每个矩形与其在第一象限内的顶点对应.这 是一一对应. 如果存在一个横坐标 a,使横坐标为 a 的点对应的矩形有无数个,即可选择所有横坐标为 a 的矩形,把这些矩形按纵坐标从小到大排序,按此排序得出的矩形序列即满足题意. 同理, 如果存在一个纵坐标 b, 使纵坐标为 b 的点对应的矩形有无数个, 亦可如上证得解. 现设对于任何给定正整数 a 与 b,矩形(a,y) 只有有限个,矩形(x,b)也只有有限个. 先取 a1,使 a1 为所有矩形的横坐标的最小值,它对应着矩形(a1,y)只有有限个,取其中 y 值最小的一个为矩形(a1,b1),据题意,矩形集合{(x,y)|x?a1,或 y?b1}是有限集.(这是 因为:由假设,所有横坐标为 1,2,?,a1-1,a1 的矩形的集合都为有限集,所有纵坐标为 1,2,?,b1-1,b1 的矩形集合也都为有限集)把这些矩形去掉后的矩形集合仍为无限集.对 新的矩形集合,再按此步骤又可得第二个矩形(a2,b2),第一个矩形在此矩形内部. 这一过程可以无限继续下去,于是本题获证. 10.证明 如果存在某个正 n 边形,它的每个顶点都是整点,设为正多边形 ABC?.现在 平面上任取一个整点 O,作 OA1∥AB,且 OA1=AB,则由于 A、B、O 均为整点,得 A1 为整 点.作 OB1∥BC,且 OB1=BC,则 B1 也是整点,??,这时得到一个新的多边形 A1B1?, 此新多边形是一个格点多边形,且多边形 A1B1?也是正多边形.但当 n?7 时,A1B1<AB,即 新的整点正多边形的边长小于原来的整点正多边形的边长.这一过程可以无限进行下去.这 是不可能的.即不存在边数不小于 7 的整点正多边形 11.证明 不妨设三个箱子中的球数分别为 a,b,c,且 0<a?b?c. 于是存在 q,r∈N,使 b=aq+r(0?r<a). - - 用二进制写出 q:q=2k+ε1?2k 1+ε2?2k 2+?+εk-1?2+εk.(εi∈{0,1}) - - 故 b=a(2k+ε1?2k 1+ε2?2k 2+?+εk-1?2+εk)+r. 现按如下规则操作: ⑴第一次操作:若 εk=1,则在第二箱中取出 a 个球放入第一箱中,此时,第一箱中球数 - - - 为 2a,第二箱中球数为 2a(2k 1+ε1?2k 2+ε2?2k 3+?+εk-1)+r; 若 εk=0,则在第三箱中取出 a 个球放入第一箱中,此时第一箱中球数为 2a,第二箱中球

为为 b,第三箱中球数=c-a?a(2k+ε1?2k 1+ε2?2k 2+?+εk-1)+r ⑵ 第二次操作: εk-1=1, 若 则在第二箱中取出 2a 个球放入第一箱, 此时第一箱的球 22a, - - - 第二箱中球数为 22a(2k 2+ε1?2k 3+ε2?2k 4+?+εk-2)+r,若 εk-1=0,则在第三箱中取 2a 个球 放入第一箱中; ?????? - -- 一般的,第 i(1?i?k)次操作后,第一箱中球数为 2ia,第二箱中球数为 2i(2k i+ε1?2k i -i-2 -1 -2 1 +ε2?2k +?+εk-i)+r,第三箱中球数?(2k+ε1?2k +ε2?2k +?+εk-i)a+r-(2i-1)a - - k =(2 +ε1?2k 1+ε2?2k 2+?+εk-i?2i-2i+1)a+r. 经过 k+1 次操作,第一箱中球数为 2k+1a,第二箱中球数为 r,第三箱中球数?r.即三箱 中球数最少的为 r.r<a.这算一轮操作. 若 r>0.则重新按上述规则再进行一轮操作.于是又得最少的一箱中球数 r1 满足 0<r1 <r. 这样的操作不可能进行无限轮,必经过有限的 n 轮,使 rn=0.故证. 12.证明:如果两人不是仇人,就称这两人为朋友.把这 2n 个人任意排列成一圈,如果 相邻两人是朋友,就把他们连一条线.这时这个圈就断成若干段. 现从某一人出发,顺时针检查,遇到第一个断开 的地方,例如相邻 A B 的 A1 与 B1 间断开.现从 B1 下面的人开始检查每个 与 A1 的朋友: 必能 找到相邻两人 A2、B2,其中 A1 与 A2 是朋友,B1 与 B2 也是朋友, 这样 的两个人是能找到的:反设每个与 A1 是朋友的人后 面的人都是 B1 的 仇人,由于 A1 的朋友至少有 n 个,而 B1 的仇人不超 过 n-1 个,故不 B A 会出现这种情况. 现在把此圆周上从 B2 顺时针向后直到 A1 的一段 不动,而把从 B1 到 A2 的一段保持相邻关系翻转,使 A2 转到 A1 后面而 B1 转到 B2 前面.这样,除 A1、A2 及 B1、B2 由原来不相邻变为相邻外其余的人的相邻关系没有改变,而此时原来 A1B1 断开之处已 被 A1A2 连接替代.即断开处至少减少了 1 处. 由于圆圈上断开处只有有限处,而每经过这样一次调整可以使断开处减少 1 处.故经过 有限次调整,就能得到满足要求的坐法.
- -
1 1 2 2

用逐次调整法证明排序不等式


相关文章:
2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖
2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区...证 明在余下的部分中还能嵌入 9 个半径为 1 的圆盘,这些圆盘相互间没有 ...
2012江苏省数学竞赛《提优教程》教案:第05讲 子集
2012江苏省数学竞赛《提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 ...
2012江苏省数学竞赛《提优教程》教案:第36讲__同_余
2012江苏省数学竞赛《提优教程》教案:第36讲__同_余_学科竞赛_高中教育_教育...6. 有三堆棋子的个数分别为 19,8,9.现进行如下操作:每次从三堆中的任意...
2012江苏省数学竞赛《提优教程》教案:第62讲__多项式
2012江苏省数学竞赛《提优教程》教案:第62讲__多项式_学科竞赛_高中教育_教育专区...c 有 ( ) A.1 个 B .2 个 7 4 C.3 个 2 D.无穷多个 9.多项式...
2012江苏省数学竞赛《提优教程》教案:第78讲__数论选讲
2012江苏省数学竞赛《提优教程》教案:第78讲__数论选讲_学科竞赛_高中教育_教育...若 a-c=9, 则 b-d= 2 4 (2003 年全国高中数学竞赛) 2.一组相邻的正...
2012江苏省数学竞赛《提优教程》教案:第11讲 极端原理
2012江苏省数学竞赛《提优教程》教案:第11讲 极端原理_学科竞赛_高中教育_教育专区。第十一讲 极端原理 考虑极端情况,是解决数学问题的非常重要的思考方式。在具体...
2012江苏省数学竞赛《提优教程》教案:第28讲__数列及其通项
2012江苏省数学竞赛《提优教程》教案:第28讲__数列及其通项_学科竞赛_高中教育_教育专区。第9讲 A 类例题 数列及其通项 本节主要内容:数列的基本知识,简单的递...
2012江苏省数学竞赛《提优教程》教案:第36讲--同-余
2012江苏省数学竞赛《提优教程》教案:第36讲--同-余_学科竞赛_高中教育_教育...+ a1×10+a0, ∵10≡1(mod9),∴10n≡1(mod9),∴an×10n+ an-1×10n...
2012江苏省数学竞赛《提优教程》教案:第63讲_极限
2012江苏省数学竞赛《提优教程》教案:第63讲_极限_学科竞赛_高中教育_教育专区...r n ?? 8 n 8 3 n ?4 9 9 Sn 情景再现 5 在数列{an}中, 已知 ...
2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理
2012江苏省数学竞赛《提优教程》教案:第10讲 抽屉原理_学科竞赛_高中教育_教育...8.证明:把前 39 个正整数分成下面 7 组: 1; 2,3; 4,5,6; 7,8,9,...
更多相关标签: