問題
下の図は，から始めて分数の左下に分数，右下に分数を配置するという規則でできた樹形図の一部である．このとき以下の問いに答えよ．
(1) この樹形図に現れる分数はすべて既約分数であることを示せ．ただし整数は既約分数とみなす．
(2) すべての正の有理数がこの樹形図に現れることを示せ．
(3) この樹形図に現れる有理数はすべて異なることを示せ．
(4) はこの樹形図の上から何段目の左から何番目に配置されるか答えよ．たとえば，は上から3段目の左から4番目である．
% 図は省略
方針
この樹形図は、分数 から左へ 、右へ を作る。既約性は最大公約数が保存されることから示す。任意の正の既約分数から根へ戻るには、 なら親を 、 なら親を とする。この逆操作では分子分母の和が減るため有限回で に到達し、存在が示せる。同時に逆操作は一意なので、同じ分数が2か所に現れることもない。(4)は から逆にたどって道順を求め、左を0、右を1とする2進表示で位置番号を出す。
解答
(1)
が既約であるとする。左下の分数は である。もし正の整数 が と の公約数なら、 は も割る。したがって は と の公約数である。 は既約なので であり、 は既約である。
右下の分数 についても、 と の公約数は も割るので、やはり1しかない。最初の は既約であるから、帰納的に樹形図に現れる分数はすべて既約である。
(2)
任意の正の有理数を既約分数 で表す。 とする。既約なので、このとき は起こらない。 のときは を親と考える。実際、この分数の左下は である。 のときは を親と考える。実際、この分数の右下は である。
どちらの場合も、親の分子と分母の和は、元の より小さい。したがってこの操作を繰り返すと、有限回で に到達する。逆にたどれば、任意の正の有理数 は樹形図に現れる。
(3)
(2)で用いた逆向きの操作は、既約な正の有理数に対して一意に定まる。すなわち、 なら直前は必ず 、 なら直前は必ず である。
もし同じ有理数が樹形図の2か所に現れたとすると、その有理数から根 へ戻る道が2通りあることになる。しかし逆向きの道は一意なので、これは不可能である。したがって樹形図に現れる有理数はすべて異なる。
(4)
から逆向きにたどる。
である。矢印は10本あるので、 は上から 段目にある。
根 から へ進む道順は、上の逆順を読んで である。ただし は左下、 は右下へ進むことを表す。
同じ段の左からの位置は、左を0、右を1とした2進数で決まる。上の道順は であり、これは10進法で28である。左端を1番目と数えるので、位置は 番目である。
したがって、 は上から11段目の左から29番目に配置される。