题目

一只青蛙在平面直角坐标系上从（1,1）开始,可以按照如下两种方式跳跃.
接上面题目：1、能从任意点(a,b),跳到点（2a,b)或（a,2b)
2、对于点（a,b）,如果a＞b.则能从﹙a,b﹚跳到﹙a－b,b).如果a＜b,则能从（a,b)跳到（a,b-a)
问题：这只青蛙能达到下面各点吗?能的话说出路径.
1）（3,5）
2） （12,60）
3） （200,5）
4） （200,6）

提问时间：2021-03-13

答案

（1）能到达点（3,5）和点（200,6）．
从（1,1）出发到（3,5）的路径为：
（1,1）→（2,1）→（4,1）→（3,1）→（3,2）
→（3,4）→（3,8）→（3,5）．
从（1,1）出发到（200,6）的路径为：
（1,1）→（1,2）→（1,4）→（1,3）→（1,6）→（2,6）→（4,6）
→（8,6）→（16,6）→（10,6）→（20,6）→（40,6）→（80,6）
→（160,6）→（320,6）→（前面的数反复减20次6）→（200,6）；
（2）不能到达点（12,60）和（200,5）．
理由如下：
∵a和b的公共奇约数=a和2b的公共奇约数=2a和b的公共奇约数,
∴由规则①知,跳跃不改变前后两数的公共奇约数．
∵如果a＞b,a和b的最大公约数=（a-b）和b的最大公约数,
如果a＜b,a和b的最大公约数=（b-a）和b的最大公约数,
∴由规则②知,跳跃不改变前后两数的最大公约数．
从而按规则①和规则②跳跃,均不改变坐标前后两数的公共奇约数．
∵1和1的公共奇约数为1,12和60的公共奇约数为3,200和5的公共奇约数为5．
∴从（1,1）出发不可能到达给定点（12,60）和（200,5）．