 コメント ( No.8 ) |
- 日時： 2012/08/31 13:41
- 名前： ケンスー
- ずーっと放置されていた問題ですが、ようやく解答を公開することになりました。いまさら公開しても、覚えている方はおそらくいないし、見る方もいらっしゃらないでしょう。とはいうものの、全てはここまで放置していた自分の責任ですので、公開します。これを機に猛省し、今後はきちんとした問題管理を行っていきたいと思います（もっとも、そうあるのが当然のことなのですが）。
以下解答。
いいたいことはいくつかあるのですが、とりあえず簡単に解答を。
(解答)
条件よりA=n/m(nとmは互いに素な整数,n<m)とあらわすことが出来る。
次の操作を繰り返すことにより条件を満たす方法でAを分解できることを示す。
（操作）
n=1のとき、X=1/Aとし、操作を終了する。
Aを超えない最大の単位分数の分母をX(すなわち1/X < A < 1/(X-1))として、
A - 1/X=(nX-m)/mX
をあらたにAとする。つまり、
nX-m→n,mX→m
である。ただし約分できる場合は約分する。
（操作終わり）
示さなければならないのは
(1)操作が有限回で終了する
(2)各操作内で現れる単位分数1/Xはすべて異なる。
の二つである。
(1)
X=[m/n]+1より、
X-1 < m/n
∴nX-m<n
これは、Aの分子が小さくなっていくことを表す。
よって操作は高々n回で終わる。
(2)
X≧2より、
A- 1/X < 1/X
よって分母は大きくなっていく。
以上より、Aは各操作で作られる1/Xの総和で表すことが出来る。
よって題意は満たされた。
(解答終)
例えば、9/20を分解するとき
9/20 = 1/3 + 7/60
7/60 = 1/9 + 1/180
よって
9/20 = 1/3 + 1/9 + 1/180
ところが、これが最も簡単な分解というわけではなく、
9/20 = 1/4 + 1/5
のように、さらに簡単な分解が存在することも多いです。
さて、この問題の原点は、たしか「エジプトでは全ての分数を単位分数の和で表す」ということを聞いたのが元だったと記憶しています。「ほんとかよ・・・」と思いながら国語の授業中にこの問題を考えていました 
改めて調べてみると、どうやら上の解法は、中世、フィボナッチが考えた「強欲算法」というものと同じみたいです。フィボナッチも、強欲算法はときに複雑な単位分数展開を与える、ということを指摘しており、この方法ははじめのとっかかりにのみ使うべきで、後は恒等式などを用いて分解することを奨めています。
現代でも、この問題に関するたくさんの未解決問題がまだまだ残っています。例えば「もっとも簡単な分解を与えるアルゴリズム」といったものもあります（簡単のとらえ方には「項数が最小」「分母の総和が最小」などいくつかあるようです）。
|
|
FAQ
RSS