問題
下の図は，から始めて分数の左下に分数，右下に分数を配置するという規則でできた樹形図の一部である．このとき以下の問いに答えよ．
(1) この樹形図に現れる分数はすべて既約分数であることを示せ．ただし整数は既約分数とみなす．
(2) すべての正の有理数がこの樹形図に現れることを示せ．
(3) この樹形図に現れる有理数はすべて異なることを示せ．
(4) はこの樹形図の上から何段目の左から何番目に配置されるか答えよ．たとえば，は上から3段目の左から4番目である．
% 図は省略
方針
解法1
子へ進む操作で最大公約数が保存されることを示す。任意の既約分数からは、大きい方から小さい方を引く逆操作で根へ戻り、分子分母の和が減ることから有限性を示す。逆操作の一意性で重複も否定し、(4)は左右の道を2進数へ変換する。
解法2
分数を正の整数の組 と見て、左操作 、右操作 を扱う。逆向きの引き算算法で存在・一意性を同時に示し、(4)ではユークリッドの互除法の商で同じ向きの移動をまとめて求める。
解答
解法1
(1)
が既約なら
である。根 は既約なので、帰納的にすべて既約である。
(2)
正の既約分数 から親へ戻る操作を考える。
である。既約なので は 以外では起こらない。この操作で分子分母の和は必ず減るから、有限回で に到達する。道を逆にたどれば、任意の正の有理数が樹形図に現れる。
(3)
親は なら左上、 なら右上と一意に決まる。したがって根までの道も一意であり、同じ有理数が異なる2か所に現れることはない。
(4)
逆向きにたどると
である。矢印は10本なので11段目である。根からの道は
である。左を0、右を1とすれば で、10進数では28である。左端を1番目と数えるので
となる。よって11段目の左から29番目である。
解法2
(1)
左操作と右操作は
である。どちらも2成分の最大公約数を変えない。始点 の最大公約数は1だから、現れる組はすべて互いに素である。
(2)
互いに素な正整数の組 に対して、大きい成分から小さい成分を引く。この操作は成分を正に保ち、和を減らす。したがって有限回で等しい2成分に到達し、互いに素なのでその組は である。各引き算を逆にすれば または となるため、すべての正の有理数が現れる。
(3)
なら最後の操作は必ず 、 なら必ず である。したがって逆向きの各段階が一意で、根からの語 も一意になる。よって重複はない。
(4)
互除法の商を使うと、逆向きの同じ操作をまとめられる。
より、 から根へ戻る道は
である。逆順にして根からの道は
となり、移動は10回なので11段目である。
ある段で左から 番目の点の左の子は次の段の 番目、右の子は 番目である。 から上の道を進むと
となる。よって11段目の左から29番目である。