利用转化思想解竞赛题

《利用转化思想解竞赛题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011年第5期l3利甩转化思想解竞赛题宋强中图分类号：O142文献标识码：A文章编号：1005—6416(2011)05—0013—06对于某些竞赛题，用常规的思考方法去故(，n+1)+(m+1)-2(k+1)~0(mod4)．解答往往事倍功半，若通过一些转化思想(2)斜率为(如映射、染色、图论、概念转换等)，就可以简捷地解决问题．本文通过文献[1]中的几号((p’q)=1’1≤p≤≤g≤m)的直线，其每一条与中的单位正方形道赛题加以阐述．，的顶点一一对1映射法应(如图1，点(，Y)与(+q，m例1设n为正整数．有一个矩形ABCDY+p)在同一条的边长为AB：90n+1，B

2、C=90n+5．用水平与竖直的线将矩形分成(90n+1)×(90n+5)斜率为卫的直g个单位正方形，．s是由所有单位正方形的顶线上)，且图1点构成的集合．证明：通过s中至少两个点的直线的条数可以被4整除．(2008，巴尔干地区数学奥林匹克){fP(m『+1)+g(m+1)。珈，p≤詈，g≤詈；证明首先证明一个引理．I(ra+1一JP)(m+l-q)～，>詈戢g>孚下if／,．引理已知正奇数m、m(m

3、=对称的直线斜率所有至少通过Js中两个点的直线的集合．则为卫ITI§O(rood4)铮lVIE1(mod2)，，易知，该直线也在T中．故与(2)中直其中，V={(P，q)IP、q为奇数，1≤p≤m

4、，V={(P，q)Ip、q为奇数，1≤p≤m，1≤m；m-k(mod4)(k∈{1，3})，q≤m，(P，q)=1}．收稿日期：2010—10—14显然，(1，1)∈，且当g≤m时，有l4中等数学(P，q)EV骨(q，P)EV．显然，操作b。=l两次等价于b=0，即故lVl=0(mod2)兮fVI一1(mod2)．不操作．回到原题．故操作b=I(i=1，2，⋯，n)至多一次．取m=90n+1，m=90n+5．下面的运算规则为：1+1=0，0—1=1，当q=90n+3时，由即在模2的意义下运算．(q-p，g)=(P，q)，由题设知k一1知1，2，⋯，q中与g互质的数的一半为奇数

5、．n=∑6(1，2，⋯，n)，1故P有÷厶(90凡+3)种取值．其中，下标是在模n的意义下．1从而，每一组操作(b，b，⋯，b)对应一当q：90n+5时，P有÷(90n4-5)一1厶个满足条件的状态(a，a，⋯，a)，记为种取值(同上，且去掉P=90n+3的取值)．b1，b2，⋯，b)=(a1，a2，⋯，a)．1对一组操作(6。，b，⋯，6)，下面计算有故ll：÷((9on+3)+(90几+5))一1厶多少组与(b。，b：，⋯，b)不同的(b：，b，⋯，1=1((3)(3On+1)+(5)妒(18n+1))一1b：)满足厶b，b，⋯，b)=b：，b，⋯，6：)．①i1(mod

6、2)．易知，式①等价于所以，ITI-0(rood4)．t一1—l例2设it／,、k(n≥k≥1)为正整数．有n∑b=∑6-i(1，2，⋯，n)．②盏灯放在圆周上，且都是关着的．每一次，你由式②又有可以改变任意相邻的k盏灯的开或关的状k∑b=∑6③态，在下列三种情形下：(1)k是奇质数，②一③得6i—b=b：一6：即(2)k是奇数，b：一bi=6：一—b．(3)k是偶数，设C=b：一b．则对于2种可能的状态中有多少种状态可以c=cⅢ=cm(i=1，2，⋯，n；t=1，2，⋯)．④通过若干次操作得到?设n，k)=d，n=nod，k=kod，(nO，k0)：1．(2009，意大利国

7、家队选拔考试)考虑{nO$+1ls=1，2，⋯，0}，其模k0两解将圆周上的n盏灯依次编号为1，两不同余．2，⋯，n．于是，存在E{1，2，⋯，k。t，使得在可以通过若干次操作得到的一种状后0l(no$+1)，即kot=nos+1，贝U态中，将第i(=1，2，⋯，n)盏灯赋一个值kt=珊+d．aE{0，1}，其中，0表示灯是关着的，1表示将上式代人式④得灯是开着的．Ci=ci+h：c++dci+d(i=1，2，⋯，n)．将每次操作赋—个值bi(iE{1，2，⋯，n})：故每一组(b，b，⋯，b：)与(C