4大阪大学 2019年 数学 第4問解答・解説

・ 根の分数 $1/1$ は既約である。分数 $p/q$ が既約であるとき、左下の分数について $$\gcd(p,p+q)=\gcd(p,q)=1$$ であり、右下の分数についても $$\gcd(p+q,q)=\gcd(p,q)=1$$ である。したがって、各段を順に作ると、どの分数も既約である。分母が $1$ の整数もこの議論に含まれる。

・ 正の有理数を既約分数 $a/b$（$a,b$ は正の整数、$\gcd(a,b)=1$）で表し、$a+b$ に関する強い数学的帰納法を用いる。$a=b$ なら既約性より $a=b=1$ で、$1/1$ は根に現れる。$a<b$ なら $a/(b-a)$ は正の整数を分子・分母にもつ既約分数であり、その分子と分母の和は $b<a+b$ である。帰納法の仮定により $a/(b-a)$ は樹形図に現れ、その左下には $$\displaystyle \frac{a}{a+(b-a)}=\frac{a}{b}$$ が現れる。$a>b$ なら $(a-b)/b$ は既約で、その分子と分母の和は $a<a+b$ である。帰納法の仮定により $(a-b)/b$ は現れ、その右下には $$\displaystyle \frac{(a-b)+b}{b}=\frac{a}{b}$$ が現れる。よってすべての正の有理数が現れる。

・ (1)より、樹形図の分数はすべて既約である。根以外の分数 $a/b$ では $a\ne b$ である。$a<b$ の分数は左の子としてのみ作られ、その親は $a/(b-a)$ である。$a>b$ の分数は右の子としてのみ作られ、その親は $(a-b)/b$ である。したがって親は分数の値から一意に定まる。また、この親を作るたびに正の分子と分母の和が小さくなる。よって親をたどると有限回で根 $1/1$ に至り、その経路は一意である。したがって、同じ有理数が異なる位置に現れることはない。

・ 親から子への移動を順に書くと $$\displaystyle \frac11\xrightarrow{\mathrm{左}}\frac12\xrightarrow{\mathrm{左}}\frac13\xrightarrow{\mathrm{左}}\frac14\xrightarrow{\mathrm{左}}\frac15\xrightarrow{\mathrm{左}}\frac16\xrightarrow{\mathrm{右}}\frac76\xrightarrow{\mathrm{右}}\frac{13}{6}\xrightarrow{\mathrm{右}}\frac{19}{6}\xrightarrow{\mathrm{左}}\frac{19}{25}\xrightarrow{\mathrm{左}}\frac{19}{44}.$$ 移動は10回なので上から11段目にある。ある段で左から $k$ 番目の分数の子は、次の段では左の子が $2k-1$ 番目、右の子が $2k$ 番目となる。最初の5回の左移動では位置は1番目のままであり、続く3回の右移動で2番目、4番目、8番目となる。最後の2回の左移動で15番目、29番目となる。したがって、上から11段目の左から29番目である。