第13讲奇偶分析(原)13讲）第13讲奇偶分析第13讲

《第13讲奇偶分析(原)13讲）第13讲奇偶分析第13讲》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第13讲奇偶分析法把全体整数按被2除的余数分为两类：被2除余数为0整数的称为偶数，一般表示为2R伙为整数），被2除余数为1整数的称为奇数，-•般表示为2好1伙为整数）.由于既不会有一个整数同时出现在奇数类和偶数类，也不会有一个整数既不在奇数类乂在偶数类，因此，我们可以把对整数问题的研究转化为对奇数和偶数的研究.这种利用奇偶数分析问题的方法就可以使一些看起来比较困难的题II变得简单易解了.奇偶分析利用了奇数与偶数的一些性质：1、奇数不等于他数；2、在自然数数列中，奇数与偶数是相间排列的；3、奇数土奇数二偶数，偶数土偶数二偶数，奇数土偶数二

2、奇数；奇数个奇数的和是奇数，偶数个奇数的和是偶数，任意个偶数的和是偶数；4、奇数X奇数=奇数，偶数X偶数=4的倍数，偶数X整数=偶数；5、两个梏数的和与这两个整数的差具有相同的奇偶性6、奇数的平方被4除余1,偶数平方为4的倍数；奇偶分析也常表现为染色，把一个图形染成黑白两色，往往可视为其屮一色为奇数，另一色为偶数；也可视为用+1与-1（或1与0）标号，……总Z,在分成两类对问题进行讨论时，常常可以看成是在进行奇偶分析.例1⑴证明：平面上的格点中，任取五点，必有两点，其连线中点是格点.（2）至多可以取岀多少个格点，使这些点中任取三点为顶点

3、的三角形面积都不是整数.（1）分析按横处标与纵坐标的奇偶性把平面格点分类，用抽屉原理证明.证明按横坐标与纵坐标的奇偶性把平而上的所有格点分类，共有4类：（奇，奇），（奇，偶），（偶，奇）,（偶,偶）.任取5个格点，必有2点属于同一类，设A（q,yj,Bg,）吩这二点是局于同一类的两点，则其连线的中点M（*（xi+x2），知1+歹2））即为格点.故得证.⑵分析考虑三角形的而积如何计算.解由三角形面积表达式S=*［（X

4、—也）（$2—旳）一（也一兀3）0厂『2）］知，如果三角形有某两个顶点属于同一类（上题中的分类），则其曲积为整数；如果三个

5、顶点都不同类，则其面枳不为整数.于是取分屈于4个不同的类的4个格点，以这4点中的任三点为顶点的三角形面积都不为整数，但如果取5个格点，则必有某两点属于同一•类，此时以这二个点及另外任一点为顶点的三角形而积为整数.故至多取4个点，II此四点应分属不同的4类.说明把整数分成“奇数”与“偶数”这两类，就相当于构造了两个抽屉，从而奇偶分析常常用抽屉原理为工具解决问题.链接在坐标系内的三角形的面积公式：为了方便，先把三角形放在第一象限内，当三角形不在第一象限内时，可利用平移公式说明结论仍然成立.如图，△A3C的三个顶点、（按逆时针旋转的顺序排列）

6、坐标分别为Pi（兀1，yj,P2（x2y力），尸3（兀3,旳）・作丄Ox,P2P2'丄Ox,P3P3'丄Ox.垂足分别为P'l，P‘2,P‘3・于是，三角形P1P2P3的面积可以表示成三个直角梯形的面积的代数和：如在左图中，s=戸©1+旳）（尤3一尤1）+（力+$2）（兀2一X3）一（）?1+V2）ta一X1）]一砂1）+（利3一兀3歹2）+（兀3力一兀1旳）]・这个式子也可写为S=

7、l（Xi-x2）（｝?2-旳）-（X2-X3）®-力）].右图也可同样计算得证.对于放置于任何位置的三角形，只要取平移公式代入检查即知该结果正确.例2设山

8、，如…'064是1，2,…，63,64的任意一种排列.令b=a—a^,Z?2=l^3—Q』，•••，方32=匕63—。64〔；C=b[一/加，©=1方3—加1，…，C16=I〃31—加21；d

9、=k?[—C2I,d2=k?3—C4I,…，“8=915—cQ;这样一直作下去，最后得到一个整数X.求证：兀为偶数.分析可以从后向前推：若X为奇数，则其前一次运算时的两个数必一奇一偶，…，这样直到开始时的64个数的奇偶性.这就是证法一的思路；也可以从前向后推：第一次运算得到的32个数的奇偶性与原来各数的奇偶性有什么关联？笫二次运算所得1

10、6个数又与笫一次运算的32个数有什么关联？又少原來的64个数有何关联？…，这样直到最后一个数.这就是证法二的思路.证法一假定兀为奇数，则上述计算过程中倒数第二步的两个数是一奇-•偶，倒数第三步的四个数或者是三奇一偶或者是一奇三偶.仿此推知，计算过程屮的每一步只能有奇数个奇数，那么在⑦，勿，…，％4,中也该有奇数个奇数•但它们是1,2,…，64的某一排列，其中奇数有32个,这就产生了矛盾•所以最后一个数只能是偶数.证法二因为整数。与⑷的奇偶性一致，整数°、b的和o+b与其差a-b的奇偶性也一致，所以上述计算过程的第二步中的32个数：ld[

11、—血，1。3—心1，…，1。63—伽1，分别与。1+。2'心+如，…，伽+伽，的奇偶性一致，于是，原来的计算过程可改为考虑：第一•步：°1，。2'…，。64；第―步：Cl+Cl2y他+心，…，。63+。6