FC2ブログ

Welcome to my blog

[答510] 近い値の分数

ヤドカリ

ヤドカリ



[答510] 近い値の分数


 分子も分母も 1000以下の自然数である分数のうち、その値が 0.8451 より小さくて最も近いものは?


[準備]

 解答にピックの定理( https://okayadokary.blog.fc2.com/blog-entry-568.html 参照)を使います。

 [ピックの定理] 格子点を頂点とする多角形について次の式が成り立ちます。

  (面積)=(内部の格子点の数)+(頂点や辺上の格子点の数)/2-1

  以下の解答では、(内部の格子点の数)=(面積)+1-(頂点や辺上の格子点の数)/2 を使います。


[解答1] 連分数を意識して

 10000/8451=1+1549/8451,8451/1549=5+706/1549,1549/706=2+137/706,

  706/137=5+21/137,137/21=6+11/21,21/11=1+10/11,11/10=1+1/10 です。

 1<21/11<2 → 1>11/21>1/2 → 7>137/21>13/2 → 1/7<21/137<2/13 → 36/7<706/137<67/13

  → 7/36>137/706>13/67 → 79/36>1549/706>147/67 → 36/79<706/1549<67/147

  → 431/79<8451/1549<802/147 → 79/431>1549/8451>147/802

  → 510/431>10000/8451>949/802 → 431/510<8451/10000<802/949

 1<11/10<2 から始めるとより詳しく 1233/1459<8451/10000<802/949 が得られますが、

  分子分母が 1000を越してしまいます。

 よって、答の候補として 431/510 を得ます。

 次に、座標平面上で、格子点(a,b) に対して (0,0),(a,b) を結ぶ直線の傾き b/a を対応させると、

 領域 (431/510)x<y<(8451/10000)x,x≦1000 に格子点がなければ、431/510 が答えです。

 O(0,0),A(10000,8451),B(510,431),C(1020,862) として、

 線分上の端点以外の格子点の数を求めると、

 線分OA:GCD(10000,8451)-1=0 ,線分OC:GCD(1020,862)-1=1 ,

 線分AC:GCD(10000-1020,8451-862)-1=0 ,線分AB:GCD(10000-510,8451-431)-1=9 で、

 △OACの周上に格子点が 4個あることになります。

 また、△OAC=|10000・862-8451・1020|/2=10 だから、

 ピックの定理により、△OACの内部の格子点の数は、10+1-4/2=9 個で、これは線分AB上の格子点です。

 その格子点は (510+949k,431+802k) (k=1,2,……,9) だから、

 領域 (431/510)x<y<(8451/10000)x,x≦1000 に格子点はありません。


[参考] ピックの定理で厳密に示した理由

 10000/8451=1+1549/8451,8451/1549=5+706/1549,1549/706=2+137/706,

  706/137=5+21/137,137/21=6+11/21,21/11=1+10/11,11/10=1+1/10 ですが、

 3>1549/706>2 から始めると

  → 1/3<706/1549<1/2 → 16/3<8451/1549<11/2 → 3/16>1549/8451>2/11

  → 19/16>10000/8451>13/11 → 16/19<8451/10000<11/13

 5<706/137<6 から始めると

  → 1/5>137/706>1/6 → 11/5>1549/706>13/6 → 5/11<706/1549<6/13

  → 60/11<8451/1549<71/13 → 11/60>1549/8451>13/71 → 71/60>10000/8451>84/71

  → 60/71<8451/10000<71/84

 例えば、

 16/19=0.8421052…… と 60/71=0.8450704…… の間に、次のようなものもあります。

 27/32=0.84375 ,38/45=0.84444…… ,49/58=0.84482…… 


[解答2] uch*n*anさんの解答より

 0.8451=8451/10000 を (x,y)-座標平面上の O(0,0),P(8451,10000) を通る直線の傾きと思い,

 第1象限内で,直線 y<(8451/10000)x の格子点 Q(m,n) を考えます。

 ただし,m,n は 1000 以下の互に素な自然数とします。

 すると,m,n が 1000 以下で n/m が 8451/10000 より小さくて最も近いというのは,

 O,P,Q を頂点とする三角形の内部及び PQ の両端を含まない辺上に

 x座標 及び y座標がともに 1000 以下の格子点が存在しないことです。

 そこで,話を簡単にするために,まず,三角形内に格子点がないとして調べます、

 もしこれで条件を満たす(m,n)が見つかればこれが解となります。

 条件を満たす(m,n)が見つからなければ,内部の点の個数を 1 個増やして同様に調べます。

 ( 後者は,三角形の内部に x座標 又は y座標が 1000 を超える格子点が存在する場合ですが,

  実際には,以下で見るように,前者の内部に格子点がない場合で解が見つかり,不要です。)

 この三角形の面積は,点の位置関係を考慮して,(8451m-10000n)/2 ですが,

 これをピックの定理で評価すると,gcd(10000-m, 8451-n)=g として,

 三角形の内部の格子点の個数=0,三角形の周上の格子点の個数=g+2,なので,

 (8451m-10000n)/2=0+(g+2)/2-1,8451m-10000n=g,

 8451-n=ga,10000-m=gb とすると,m=10000-gb,n=8451-ga,

 8451(10000-gb)-10000(8451-ga)=g,10000a-8451b=1

 この不定方程式を解くと,t を整数として, a=802+8451t,b=949+10000t

  (この部分は連分数の計算と同様にユークリッドの互除法がポイントになり,計算が面倒。)

 10000-m=g(949+10000t),8451-n=g(802+8451t)

 m,n は 1000 以下の互に素な自然数なので,

 t=0,g=10,10000-m=9490,8451-n=8020,m=510,n=431

 このとき,三角形の内部に格子点はなく,PQ 上の Q(m,n) に一番近い点は (1233,1459) なので,

 この (m,n) は条件を満たしています。

 そこで,8451/10000 より小さくて最も近い分数は 431/510 になります。


[解答3]

 0.8451=8451/10000>8450/10000=169/200 (約分できてかなり簡単になるのがミソ) です。

 座標平面上で、格子点(a,b) に対して (0,0),(a,b) を結ぶ直線の傾き b/a を対応させます。

 O(0,0),A(10000,8451),D(200,169) をとり、平行四辺形OAEDを作れば、E(10200,8620) となり、

 OEの傾きは 8620/10200=431/510 (ここでも約分できてかなり簡単になるのがミソ) です。

 GCD(200,169)-1=0,GCD(10000,8451)-1=0 だから、

 平行四辺形OAEDの周上の格子点は頂点の4個で、

 平行四辺形OAED=|200・8451-169・10000|=200 になり、

 ピックの定理より、平行四辺形OAEDの内部の格子点の数は、200+1-4/2=199 個で、

 すべて 対角線OE上の (510k,431k) (k=1,2,……,199) です。

 よって、OEの傾き 431/510 が答になります。

☆ 大きい方で近い 802/949 ですが、こんなに簡単に出ません。


[背景]

 log107≒0.8451 ですが、これに近い分数を求めました。

 7510≒1.0000009377765355・10431≒10431 なので、log107≒431/510 ですが、

 log107=0.8450980400……,431/510=0.8450980392…… は小数第7位まで一致します。

.

スポンサーサイト



Comments 20

There are no comments yet.
ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!を有難う御座います。
白い小さな花が集まって咲いている姿は好きな光景です。
仰る通り、マーガレットやデージーに似ていますね。

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!を有難う御座います。
小さな花が集団で咲いていると見ごたえがあります。
小菊はそういう意味でも綺麗です。

古い人  
No title

小菊シリーズですね。

数多くある菊でも此れだけ多く咲くと見事ですね。
ナイス。

アキチャン  
No title

綺麗ですね(o^-^o)

uch*n*an  
No title

これは,見かけよりも難しい問題だったと思います。
私の解法は二つ。(解法1)は大分手を抜きましたが[解答1],(解法2)は[解答2],でした。
それで満足してしまったのですが,[解答3]は,なるほど,ですね。

スモークマン  
No title

グーテンターク ^^
これは...それ以外ないかを詰め切れないままでした...^^;
ピックの定理というヒントいただくも...使い切れず...
面白い応用ですね☆
連分数も浮かんで計算しかけたんですが...わけががわからなくなり...
挫折...^^;
Orz~

たけちゃん  
No title

この問題でピックの定理は浮かびませんでした.勉強になりました.

ただ,本当にそのように示すことが必要なのかは,やや疑問に思います.
私にとっては,
「[485]2の累乗の最高位の数字」のときに考えたことのおさらい
なのですが,以下,連分数を
1/(a+1/b) を [a,b],1/(a+1/(b+1/c)) を [a,b,c]
などのように表すことにします.
1未満の正の有理数は,有限連分数で表され,その末尾は2以上の自然数です.
(また,形式的に,[…,a,1]=[…,a+1]と見ることができます.)

たけちゃん  
No title

[解答1]で得られた不等式
431/510<8451/10000<802/949
は,連分数表示すると,
[1,5,2,5,7]<[1,5,2,5,6,1,1,10]<[1,5,2,5,6,2]
となります.
ここで確かめるべきは,
[1,5,2,5,7]<x<[1,5,2,5,6,1,1,10] を満たす,
分子分母が1000より小さい分数xがないこと…(*)ですね.

ところが,この範囲の分数は,連分数表示で,
[1,5,2,5,6,1,…]と表され,
[1,5,2,5,6,1,2]=1233/1459なので,(*)は当然成り立つと思います.

たけちゃん  
No title

参考までに,プログラムで,8451/10000以下の分数で,
できるだけ大きいものを順次求め.
合わせて連分数表示したものを提示しておきます.
よりよい近似が,連分数ではどのように得られているかがはっきりすると思います.

(有理数モード前提です)
SUB P(x)
DO WHILE x>0
LET x=1/x
PRINT INT(x);
LET x=x-INT(x)
LOOP
PRINT
END SUB
LET m=0
FOR i=1 TO 10000
LET j=INT(i*8451/10000)
IF j/i>m THEN
LET m=j/i
PRINT j;"/";i,
CALL p(j/i)
END IF
NEXT I
end

たけちゃん  
No title

1 / 2 2
2 / 3 1 2
3 / 4 1 3
4 / 5 1 4
5 / 6 1 5
16 / 19 1 5 3
27 / 32 1 5 2 2
38 / 45 1 5 2 3
49 / 58 1 5 2 4
60 / 71 1 5 2 5
431 / 510 1 5 2 5 7
1233 / 1459 1 5 2 5 6 1 2
2035 / 2408 1 5 2 5 6 1 1 2
2837 / 3357 1 5 2 5 6 1 1 3
3639 / 4306 1 5 2 5 6 1 1 4
(中略)
7649 / 9051 1 5 2 5 6 1 1 9
8451 / 10000 1 5 2 5 6 1 1 10

uch*n*an  
No title

はい,私が手を抜いたというのは,そのように考えてもいいかな,
と思ったからです。
そして,実際,連分数の理論からは正しいのですが,
その議論なし必要十分になっているのか,ちょっと不安な気もしました。

ヤドカリ  
No title

古い人さん、早速のコメントとナイス!を有難う御座います。
仰る通りよく見かけます。
白いありふれた菊もこれだけ集まると見事です。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難う御座います。
見事に咲いていました。
私は撮るだけですが、育てておられる人は偉いなぁといつも思います。

ヤドカリ  
No title

uch*n*anさん、2度にわたるコメントを有難う御座います。
私は[解答3]と[背景]だけを用意していたのですが、
みなさん、連分数がお好きなようでしたので、あわてて[解答1]を書きました。
[背景]のように、7の累乗を話題にしたかったのですが、
みなさん、あまり興味を持たれなかったのが残念です。

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
uch*n*anさんも記されているように、見かけよりも難しい問題だったようです。
私は、[解答3]のように大雑把に解けばよいと思っていました。

ヤドカリ  
No title

たけちゃんさん、連分数についての詳しいコメントを有難う御座います。
> [1,5,2,5,6,1,…]と表され, [1,5,2,5,6,1,2]=1233/1459なので
が、簡潔ですね。
uch*n*anさんへのコメントにも記しましたが、
近似分数は[解答3]ですませる予定でした。
[背景]の log7 の近似値を求めるのに、
7^510 という 10^431 にごく近い数があることを紹介するために
この問題を作りました。

さっちゃんこ  
No title

こんばんは
白の小菊 野菊のようにも見えますね
小さな花が寄り添う姿も可愛くて素晴らしいですね ナイス

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難う御座います。
伊藤左千夫の「野菊の墓」で、
民さんの好きだった野菊もこんな感じだったのかも知れませんね。
貴女のコメントで若き日に読んだ小説を思い出しました。

ニリンソウ  
No title

白い小菊が賑やかですね
光の具合も上手く撮れています
明日は大荒れになりそうですが今は星が綺麗に輝いています。
ナイス

ヤドカリ  
No title

ニリンソウさん、コメントとナイス!を有難う御座います。
小菊が沢山咲いているのは大輪の菊より私には魅力です。
日本海側の天気はこの時期はよく荒れますね。
当方はただただ寒いだけです。