
書記が数学やるだけ#695 ファレイ数列とスターン=ブロコット木
前回触れたファレイ数列についてより細かな性質を見ていく。
問題
スターン=ブロコット木を扱う阪大の本問は,ほぼ初見のものからいかに構造を見抜いて証明できるかを問う,差のつきやすい問題であった。

説明
ファレイ数列という名前は、イギリスの地質学者ジョン・フェアリーに因む。 1816年の「フィロソフィカル・マガジン」(Philosophical Magazine) にこの数列を扱ったフェアリーの要約論文が掲載されている。 この中でフェアリーは、ファレイ数列の各項が、隣接する数の中間数になると推測しているが、知られている限りではフェアリーはこの証明を与えていない。 コーシーはフェアリーの論文を読み、著作 Exercises de mathématique においてその証明を与え、その結果をフェアリーによるものとしている。 おそらくフェアリーやコーシーの知るところではなかったが、類似の結果は 1802 年に数学者シャルル・アロによってすでに出版されていた。 よって、この数列にフェアリーの名が与えられているのは歴史のいたずらの一つといえる。

解答
全て既約分数であることは前回も示した通りで,これは帰納的にすめすことができる。

同じ分数が現れることはないことは,生成された分数がちょうど前後の順序関係を保つことから言える。

スターン=ブロコット木は全ての正の有理数を網羅している。この場合,ある有理数があったとして,そこから木を上に辿っていく操作を繰り返すと有限回で終わる,ことを示せば良い。

最後に具体例,分母と分子の大きい方から小さい方を引くという操作を何回行うか,木の右に行くか左に行くか,を追うことができれば十分だろう。

本記事のもくじはこちら: