The frog is jumping through the cartesian coordinate systems in theplane, starting from point (1,1) according to the following rules:(i) from any point (a,b) the frog can jump to point (2a,b) or (a,2b);(ii) if a > b, the frog can jump from (a,b) to (a-b,b) and if a < b, the frogcan jump from (a,b) to (a,b-a)
Can the frog arrive to the point: (a) (24,40), (b) (40,60), (c) (24,60),(d)(200,4)?
有高手會解嗎??
有沒有比較有規則的解法
我是用倒回來算
如(24.40) 一直除2 ... (3.5) =>(3.8)=>(3.4)=>...=>(1.1)
最後得答案是a 和 d
5 則留言:
目前的想法是這樣:
如果 x 和 y 有除了 2 以外的共同因數, 則 (x,y) 到不了. 這個可以證明, 你想一下..
gcd(2a,b) = 2*gcd(a,b) or gcd(a,b)
gcd(a,2b)同理
by Euclidean algorithm,
if a>b, gcd(a-b,b) = gcd(a,b)
if b>a, gcd(a,b-a) = gcd(a,b)
另外, gcd(1,1)=1
所以gcd(x,y)= 2^k, k=0,1,2,...
也就是說x與y的gcd會是2的冪次方的形式
是的 wynne 的證明沒有錯, 小小吹毛求疵一下,
所以 gcd(x,y)= 2^k "for some k" in N∪{0}
不過要注意的是, 我們只證明了必要性, 也就是說, 若 (x,y) 可達, 則 gcd(x,y)=2^k; 我們並未證明充分性, 我也還在思考.
謝謝修正, (b)(c)選項已證出了不可行, 而(a)(d)依照題目的設計其實不難找出路徑, 我想把路徑寫下來可能是最快的方法
是啊.. 不過試著找出所有解還滿有趣的.. 雖然沒什麼想法.. 有空再想吧..
張貼留言