第4問 整数・数列の解答・解説

規則を記号で書く。分数 $\frac{p}{q}$ から

である。$\mathrm{L}$ では分母だけが増え、$\mathrm{R}$ では分子だけが増える。$n$ 段目には $2^{n-1}$ 個の分数が並ぶ。

逆向きも用意しておく。$\frac{p}{q}$ が $1$ 段目以外にあるとき、その真上（親）は

である。実際、$\frac{p}{q-p}$ に $\mathrm{L}$ を施すと $\frac{p}{p+\left(q-p\right)}=\frac{p}{q}$、$\frac{p-q}{q}$ に $\mathrm{R}$ を施すと $\frac{\left(p-q\right)+q}{q}=\frac{p}{q}$ になる。これはユークリッドの互除法の1ステップ（大きいほうから小さいほうを引く）そのものである。

段数 $n$ についての帰納法で「$n$ 段目のどの分数 $\frac{p}{q}$ も $p$ と $q$ が互いに素」を示す。

$n=1$ のとき、$\frac{1}{1}$ で $1$ と $1$ は互いに素である。

$n$ 段目の $\frac{p}{q}$ で $p,q$ が互いに素だとする。$d$ を $p$ と $p+q$ の公約数とすると、$d$ は $\left(p+q\right)-p=q$ も割り切るので $d$ は $p$ と $q$ の公約数、よって $d=1$ である。したがって $\frac{p}{p+q}$ は既約である。同様に、$p+q$ と $q$ の公約数は $\left(p+q\right)-q=p$ も割り切るので $1$ だけで、$\frac{p+q}{q}$ も既約である。

よって $n+1$ 段目の分数もすべて既約である。帰納法よりすべての段で成り立つ。$■$

正の有理数は既約分数 $\frac{p}{q}$（$p,q$ は互いに素な正の整数）としてただ一通りに書ける。この $\frac{p}{q}$ が樹形図に現れることを、$p+q$ についての帰納法で示す。

$p+q=2$ のときは $p=q=1$ で、$\frac{1}{1}$ は $1$ 段目にある。

$p+q\ge 3$ とする。$p,q$ は互いに素なので $p=q$ なら $p=q=1$ となり $p+q=2$、よって $p\ne q$ である。

1. $p<q$ のとき。$\frac{p}{q-p}$ を考える。$q-p$ は正の整数で、$\gcd \left(p,q-p\right)=\gcd \left(p,q\right)=1$ だから既約。和は $p+\left(q-p\right)=q<p+q$ なので、帰納法の仮定より樹形図に現れる。その左下が $\frac{p}{p+\left(q-p\right)}=\frac{p}{q}$ である。
2. $p>q$ のとき。同様に $\frac{p-q}{q}$ は既約で和は $p<p+q$、その右下が $\frac{p}{q}$ である。

どちらの場合も $\frac{p}{q}$ は樹形図に現れる。帰納法よりすべての正の有理数が現れる。$■$

(1) より、樹形図に現れる分数はすべて既約である。$\mathrm{L}$ で作った分数は $p<q$、$\mathrm{R}$ で作った分数は $p>q$ をみたし、$p=q$ となるのは $\frac{1}{1}$ だけである（既約で $p=q$ なら $p=q=1$）。

したがって、$\frac{1}{1}$ 以外の分数については、その値だけから

1. 左下・右下のどちらから来たか（$p$ と $q$ の大小）
2. 親が何か（$p<q$ なら $\frac{p}{q-p}$、$p>q$ なら $\frac{p-q}{q}$）

が一意に決まる。

いま、樹形図の2つの場所に同じ値 $\frac{p}{q}$ が現れたとする。(2) の降下と同じ理由で、親をとる操作を繰り返せば有限回（$p+q$ が毎回減るので）で $\frac{1}{1}$ に着く。その途中に現れる値の列も、どちらの場所から出発しても同じである。したがって2つの場所は同じ段数にあり、$\frac{1}{1}$ からの道筋（$\mathrm{L}$ と $\mathrm{R}$ の並び）も同じである。道筋が同じなら場所も同じなので、2つの場所は一致する。

よって同じ値が2か所に現れることはなく、現れる有理数はすべて異なる。$■$

(1)(2)(3) を合わせると、「正の有理数全体」と「樹形図の場所全体」が1対1に対応する。樹形図を上から順に、各段は左から右に読めば、正の有理数を重複なく並べ上げる列ができる。

$\frac{19}{44}$ から親を順にたどる。$p<q$ なら $\frac{p}{q-p}$、$p>q$ なら $\frac{p-q}{q}$ である。

ステップ数は $10$ である。$\frac{1}{1}$ が $1$ 段目なので、$\frac{19}{44}$ は

にある。

次に左から何番目かを求める。上の列を逆向きに読むと、$\frac{1}{1}$ から $\frac{19}{44}$ までの道は

である（$\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{1}{6}$ は分母が増えているので $\mathrm{L}$、$\frac{7}{6},\frac{13}{6},\frac{19}{6}$ は分子が増えているので $\mathrm{R}$、$\frac{19}{25},\frac{19}{44}$ はまた $\mathrm{L}$）。

各段では左の子が左半分、右の子が右半分に入るので、$\mathrm{L}=0$、$\mathrm{R}=1$ と読んで、最初の1歩を最上位の桁とする2進数が「左から数えた番号 $-1$」になる。実際

なので、左から $28+1=29$ 番目である。よって

である。

この読み方が正しいことは、与えられた例で確かめられる。$\frac{3}{1}$ は $\frac{3}{1}\to \frac{2}{1}\to \frac{1}{1}$ でステップ数 $2$、よって $3$ 段目。道は $\mathrm{R},\mathrm{R}$ なので $11_{\left(2\right)}=3$、左から $4$ 番目である。