Re: [求助] 數學翻譯問題

作者: LeonYo (僕は美味しいです)   2014-03-12 12:33:59
※ 引述《chliao2006 (chien)》之銘言:
: Let n be a fixed positive integer,
: and suppose we list in increasing order all numbers a/b ,
: where 1 <= a,b <= n , and the fraction a/b is in lowest terms.
: Show that if a/b and c/d are consecutive fractions in this list,
: then bc - ad = 1.
先證四條引理,以下 a, b, c, d 都是正整數.
(L1) If bc-ad=1, then (a,b)=1, (c,d)=1, (a,c)=1 and (b,d)=1.
[Pf] Suppose (a,b)=p>1. Put a=ph, b=pk.
Then bc-ad = pkc - phd = p(kc-hd)≠1.
(L2) For any fraction in its lowest term x/y with 1<x<y,
there exists two fractions a/b and c/d such that a/b < x/y < c/d ≦1,
bx-ay=1, cy-dx=1, bc-ad=1, x=a+c and y=b+d.
[Pf] Let x, y be two positive integers such that (x,y)=1 and 1<x<y.
Then there are two unique integers q, r satisfying that y = xq + r
and 0<r<x.
Since (x,r)=(x,y)=1, there exists some integer a such that 0<a<x
and ar≡-1 (mod x). Put ar = px-1.
Then px-1 = ar < xr => px-rx<1 => x(p-r)<1 => p≦r.
And since px-1 = ar >0, px>1 => p≧1.
Let b = aq + p. Then bx-ay = (aq+p)x - a(xq+r) = px-ar = 1.
Furthermore, b = aq+p < xq+p ≦ xq+r = y.
Since bx-ay=1>0, bx>ay, a/b < x/y.
Since x-a>0 and y-b>0 as discussed above, put c=x-a and d=y-b.
Then cy-dx = (x-a)y - (y-b)x = -ay+bx =1>0. Hence x/y < c/d.
And we claim c/d≦1. For if c=d+k for some k≧1,
Then cy-dx = (d+k)y-dx = d(y-x)+ky > d+ky >1.
(L3) If a/b < x/y < c/d with bc-ad=1 and bx-ay=1, then y≧b+d.
[Pf] Let a/b < c/d with bc-ad=1 be given.
Suppose there are some fraction x/y with y<b+d
such that a/b < x/y < c/d and bx-ay=1.
Since a/b < x/y < c/d, x/y - a/b < c/d - a/b.
=> 1/by < 1/bd => d > y≧b+d. (→←)
(L4) If a/b < x/y < c/d with bx-ay=1 and cy-dx=1,
then (x-1)/y≦a/b and (x+1)/y≧c/d.
[Pf] a/b - (x-1)/y = [ay-b(x-1)]/by = (-1+b)/by≧0.
(x+1)/y - c/d = [d(x+1)-cy]/dy = (-1+d)/dy≧0.
Having proved the lemmas, we now proceed to build the argument by induction.
Since the sequence are symmetric, we discuss only the left half part
of the sequence, i.e., the terms not greater than 1/1.
S_1 ={1/1}
S_2 ={1/2, 1/1}
S_3 ={1/3, 1/2, 2/3, 1/1}
We observed that S_1, S_2, S_3 are such sequencese that
every term is of the form a/b where 1≦a, b≦n, and is in its lowest term,
and that for every two consecutive terms a/b < c/d, bc-ad=1.
And apparently, 1/n is always the first term in S_n.
Let S_k be such a sequence.
Then we are proceeding to construct S_(k+1) as a such sequence.
First we locate 1/(k+1) before 1/k and (k+1)*1 - 1*k =1.
Then let x/(k+1) with 1<x<k+1 be any fraction in its lowest term.
By Lemma 2, there are two fractions p/q and r/s such that
p/q < x/(k+1) < r/s≦1 where xq-p(k+1) = r(k+1)-sx = qr-ps =1, x=p+r
and k+1=q+s. Since q<k+1, s<k+1, p/q < r/s ≦1, these two fractions
p/q and r/s must be in S_k. Hence we can just put x/(k+1) between
p/q and r/s.
But is there any other term of S_k between p/q and r/s?
Suppose there is some term of S_k u/v≠r/s following p/q.
Then qu-pv=1, and v≦k < k+1 = q+s. By Lemma 3, it is impossible.
Hence in S_k p/q and r/s must be consecutive.
By Lemma 4, since p/q < x/(k+1) < r/s and qx-p(k+1) = r(k+1)-sx = 1,
(x-1)/(k+1) and (x+1)/(k+1) will not be between p/q and r/s.
Thus p/q < x/(k+1) < r/s are exactly consecutive in S_(k+1).
總算寫完了...
不過證明寫得不太好,尤其是L2卡了好久
作者: YHank (Hank--since 2002/10)   2014-03-12 13:38:00
推一下,如果你都是自己想的我真的覺得你很神......不過看來這題很難對中學生有elegant proof了吧,我倒是很想問問原po,哪來的鬼私校國中留學班會解這種題目...= =還是學生是隨便看到一題問題就拿來問老師的?也太離譜吧= =
作者: LeonYo (僕は美味しいです)   2014-03-12 17:22:00
就把S_n排一排觀察一些規律, 然後試著把這些規律證明出來對中學生除了L2有mod要花點力氣外, 其他應該都只是計算問題

Links booklink

Contact Us: admin [ a t ] ucptt.com