《一道竞赛题的再探究》由会员分享,可在线阅读,更多相关《一道竞赛题的再探究(1页珍藏版)》请在金锄头文库上搜索。
1、巧思妙解一道竞赛题的再探究丁 龙 云(南开大学数学科学学院,300071)收稿日期:2008 - 05 - 172006年全国初中数学竞赛浙江赛区复 赛第16题是: 一只青蛙在平面直角坐标系上从点 (1 ,1)开始,可以按照如下两种方式跳跃: 能从任意一点(a,b) ,跳到点(2a,b) 或(a,2b) . 对于点(a,b) ,如果ab,则能从 (a,b)跳到(a-b,b) ;如果ab,则能从 (a,b)跳到(a,b-a) .请你思考:这只青蛙按照规定的两种方 式跳跃,能到达下列各点吗? (1) (3 ,5) ; (2) (12 ,60) ;(3) (200 ,5) ; (4) (200 ,6
2、) .如果能,请分别给出从点(1 ,1)出发到指 定点的路程;如果不能,请说明理由. 答案是能到达点(3 ,5)和(200 ,6) . 文1中探究出:按规定的两种方式跳跃 能到点(a,b)的充分必要条件是a和b的最 大公约数为2k.并对能够跳到的情形给出了 跳跃方式的构造法.文章最后还指出:设p 是一个质数.把题目中 的跳跃方式改成: 能从任意一点(a,b) ,跳跃到点 (pa,b)或(a,pb) .则从点(1 ,1)能跳跃到点(a,b)的充分 必要条件是a和b的最大公约数为pk.构造 跳跃方式的过程是类似的. 本文将对这一充分必要条件给出一个简 明的证明,并且该证明过程中也包含了一个 跳跃方
3、式的构造法.以下对更一般的跳跃规 则 和 来证明. 记a=pia0,b=pib 0,其中,a0、b0都不能被p整除.则从(a0,b0)显然可以跳到(a,b) .因此,只须证:对任意两个不被p整 除的a0、b0,若a和b互质,则可以从点(1 ,1)跳跃到点(a0,b0) .设n= maxa0,b0 ,对n做第二归纳法.归纳假设:对任意两个不能被p整除的整数c、d,若c、d互质且max(c,d) n,则可以从 点(1 ,1)跳跃到点(c,d) .若a0=b0,由a0、b0互质知a0=b0= 1.因此,不妨设a0b0=n.由于p与a0互质,存在整数u、v,使得ua0+vp= 1.于是,ua0b0b0
4、(modp) .设s是-ub0除以p的余数.则sa0+b0( -ub0)a0+b0( -b0) +b00(modp) ,且0sp,即p整除sa0+b0,且sa0+b0 pn.设sa0+b0 p=pkb 1,其中,b1不能被p整除.则maxa0,b1 n,并且由a0与sa0+b0互质知a0、b1互质.由归纳假设,可以从点(1 ,1)跳跃到点(a0,b1) ,进而可以跳跃到(a0,pk+ 1b1) = (a0,sa0+b0) ,再到(a0,b0) .同时,从上面的证明过程逆推回去,可以 找到从点(1 ,1)跳跃到点(a,b)的跳法.参考文献:1 赵肖东.一道竞赛题的探究J .中等数学,2008(5) .81中 等 数 学