大阪大学 2019年度 前期日程 第2次学力試験理系数学 第4問

(1)
$p\mathrm{/}q$ が既約なら$$\gcd (p,p+q)=\gcd (p,q)=1,\gcd (p+q,q)=\gcd (p,q)=1$$である。根 $1\mathrm{/}1$ は既約なので、帰納的にすべて既約である。

(2)
正の既約分数 $p\mathrm{/}q\mathrm{\ne }1\mathrm{/}1$ から親へ戻る操作を考える。$$\frac{p}{q}⟼\{\begin{array}{ll}{\displaystyle \frac{p}{q-p}}& (p<q),\\ {\displaystyle \frac{p-q}{q}}& (p>q)\end{array}$$である。既約なので $p=q$ は $1\mathrm{/}1$ 以外では起こらない。この操作で分子分母の和は必ず減るから、有限回で $1\mathrm{/}1$ に到達する。道を逆にたどれば、任意の正の有理数が樹形図に現れる。

(3)
親は $p<q$ なら左上、$p>q$ なら右上と一意に決まる。したがって根までの道も一意であり、同じ有理数が異なる2か所に現れることはない。

(4)
逆向きにたどると$$\frac{19}{44}\to \frac{19}{25}\to \frac{19}{6}\to \frac{13}{6}\to \frac{7}{6}\to \frac{1}{6}\to \frac{1}{5}\to \frac{1}{4}\to \frac{1}{3}\to \frac{1}{2}\to \frac{1}{1}$$である。矢印は10本なので11段目である。根からの道は$$L,L,L,L,L,R,R,R,L,L$$である。左を0、右を1とすれば $0000011100$ で、10進数では28である。左端を1番目と数えるので$$28+1=29$$となる。よって11段目の左から29番目である。

分数を正の整数の組 $(p,q)$ と見て、左操作 $L(p,q)=(p,p+q)$、右操作 $R(p,q)=(p+q,q)$ を扱う。逆向きの引き算算法で存在・一意性を同時に示し、(4)ではユークリッドの互除法の商で同じ向きの移動をまとめて求める。

(1)
左操作と右操作は$$L(p,q)=(p,p+q),R(p,q)=(p+q,q)$$である。どちらも2成分の最大公約数を変えない。始点 $(1,1)$ の最大公約数は1だから、現れる組はすべて互いに素である。

(2)
互いに素な正整数の組 $(p,q)$ に対して、大きい成分から小さい成分を引く。この操作は成分を正に保ち、和を減らす。したがって有限回で等しい2成分に到達し、互いに素なのでその組は $(1,1)$ である。各引き算を逆にすれば $L$ または $R$ となるため、すべての正の有理数が現れる。

(3)
$p<q$ なら最後の操作は必ず $L$、$p>q$ なら必ず $R$ である。したがって逆向きの各段階が一意で、根からの語 $L,R$ も一意になる。よって重複はない。

(4)
互除法の商を使うと、逆向きの同じ操作をまとめられる。$$44=2\cdot 19+6,19=3\cdot 6+1,6=6\cdot 1$$より、$(19,44)$ から根へ戻る道は$$L^2{R}^3{L}^5$$である。逆順にして根からの道は$$L^5{R}^3{L}^2$$となり、移動は10回なので11段目である。

ある段で左から $k$ 番目の点の左の子は次の段の $2k-1$ 番目、右の子は $2k$ 番目である。$k=1$ から上の道を進むと$$1\stackrel{L^5}{\to }1\stackrel{R}{\to }2\stackrel{R}{\to }4\stackrel{R}{\to }8\stackrel{L}{\to }15\stackrel{L}{\to }29$$となる。よって11段目の左から29番目である。