トップ› 大阪大学› 2019年› 理系第4問

大阪大学 2019年理系第4問解説

方針・初手

本問は分数の生成規則から、樹形図の性質を明らかにする問題である。（1）は親ノード $\frac{p}{q}$ が既約分数であると仮定し、左下・右下の子ノードも既約分数になることを数学的帰納法により証明する。最大公約数を文字でおいて矛盾を導くか、$d=1$ を示す定石を用いる。（2）は樹形図を「親から子」ではなく「子から親」へ遡る操作として捉える。任意の正の有理数 $\frac{x}{y}$ に対して、分子と分母の大小関係から親ノードが一意に定まること、および親へ遡るごとに「分子と分母の和」が減少することを利用する。（3）は (2) で考えた「親へ遡る操作」が一意に定まることから証明できる。（4）は (2) の具体例として $\frac{19}{44}$ から $\frac{1}{1}$ まで逆算し、根から下る経路（左・右の選択）を明らかにする。これを2進数と対応させることで位置を特定する。

解法1

(1)

樹形図に現れる分数がすべて既約分数であることを、段数に関する数学的帰納法で示す。

[1] 1段目の分数は $\frac{1}{1}$ であり、これは既約分数である。

[2] ある段にある分数 $\frac{p}{q}$ が既約分数であると仮定する。すなわち、$p$ と $q$ は互いに素である。このとき、左下の子ノード $\frac{p}{p+q}$ について考える。 $p$ と $p+q$ の正の公約数を $d$ とおくと、$p$ は $d$ の倍数であり、$p+q$ も $d$ の倍数である。したがって、それらの差 $(p+q) - p = q$ も $d$ の倍数となる。これは $d$ が $p$ と $q$ の公約数であることを意味するが、仮定より $p, q$ は互いに素であるため $d = 1$ となる。よって $p$ と $p+q$ は互いに素であり、$\frac{p}{p+q}$ は既約分数である。

同様に、右下の子ノード $\frac{p+q}{q}$ について考える。 $p+q$ と $q$ の正の公約数を $d'$ とおくと、$p+q$ と $q$ はともに $d'$ の倍数であるから、差 $(p+q) - q = p$ も $d'$ の倍数となる。よって $d'$ は $p$ と $q$ の公約数となり、$d' = 1$ を得る。したがって $p+q$ と $q$ は互いに素であり、$\frac{p+q}{q}$ も既約分数である。

以上 [1], [2] より、数学的帰納法によりこの樹形図に現れる分数はすべて既約分数である。

(2)

すべての正の有理数は、互いに素な自然数の組 $(x, y)$ を用いて既約分数 $\frac{x}{y}$ として一意に表される。 (1)より、樹形図上の分数はすべて既約分数であるため、逆に任意の正の既約分数 $\frac{x}{y}$ から規則を逆算して $\frac{1}{1}$ に到達できるかを示す。

ノード $\frac{x}{y}$ $\left(\frac{x}{y} \neq \frac{1}{1}\right)$ の親ノードは、生成規則から次のように一意に定まる。・ $x < y$ のとき、$\frac{x}{y}$ は親の左下の子として生成された形 $\frac{p}{p+q}$ であるから、親ノードは $\frac{x}{y-x}$ である。・ $x > y$ のとき、$\frac{x}{y}$ は親の右下の子として生成された形 $\frac{p+q}{q}$ であるから、親ノードは $\frac{x-y}{y}$ である。（$x$ と $y$ は互いに素な自然数であるため、$x=y$ となるのは $\frac{1}{1}$ のみであり、途中で $x=y$ となることはない。）

ここで、分数 $\frac{x}{y}$ に対し「分子と分母の和 $S = x+y$」を考える。 $\frac{x}{y}$ $\left(\neq \frac{1}{1}\right)$ から親ノードを求めたときの分子分母の和 $S'$ は、・ $x < y$ のとき、$S' = x + (y-x) = y < x+y = S$ ・ $x > y$ のとき、$S' = (x-y) + y = x < x+y = S$ となり、親ノードへ遡るごとに和は必ず真に減少する。

分子と分母の和は自然数であり、最小値は $\frac{1}{1}$ のときの $1+1=2$ である。親を遡るごとに和が真に減少する自然数であるため、有限回この逆操作を繰り返せば、必ず和が2の $\frac{1}{1}$ に到達する。逆に言えば、$\frac{1}{1}$ からその経路を順に下ることで、任意の正の既約分数 $\frac{x}{y}$ に到達できる。よって、すべての正の有理数がこの樹形図に現れる。

(3)

(2)で示した通り、樹形図上の任意の分数 $\frac{x}{y}$ $\left(\neq \frac{1}{1}\right)$ に対して、その親ノードは分子と分母の大小関係によってただ1つに決定される。したがって、任意の有理数 $\frac{x}{y}$ から根である $\frac{1}{1}$ へ向かって親を遡る経路は一意に定まる。

もし仮に、ある有理数 $\frac{x}{y}$ が樹形図の異なる2箇所に現れたとする。それら2つのノードから $\frac{1}{1}$ へ向かって親を遡ると、各ステップでの親が一意であるため、完全に同じ経路を辿って $\frac{1}{1}$ に到達することになる。これは根 $\frac{1}{1}$ から $\frac{x}{y}$ へ下る経路がただ1通りしかないことを意味しており、異なる2箇所に現れるという仮定に矛盾する。よって、この樹形図に現れる有理数はすべて異なる。

(4)

(2)の手順を用いて $\frac{19}{44}$ から $\frac{1}{1}$ まで遡り、経路を特定する。左下へ進むことを L、右下へ進むことを R とする。

$\frac{19}{44}$ : $19 < 44$ より左の子 (L)。親は $\frac{19}{44-19} = \frac{19}{25}$
$\frac{19}{25}$ : $19 < 25$ より左の子 (L)。親は $\frac{19}{25-19} = \frac{19}{6}$
$\frac{19}{6}$ : $19 > 6$ より右の子 (R)。親は $\frac{19-6}{6} = \frac{13}{6}$
$\frac{13}{6}$ : $13 > 6$ より右の子 (R)。親は $\frac{13-6}{6} = \frac{7}{6}$
$\frac{7}{6}$ : $7 > 6$ より右の子 (R)。親は $\frac{7-6}{6} = \frac{1}{6}$
$\frac{1}{6}$ : $1 < 6$ より左の子 (L)。親は $\frac{1}{6-1} = \frac{1}{5}$
$\frac{1}{5}$ : $1 < 5$ より左の子 (L)。親は $\frac{1}{4}$
$\frac{1}{4}$ : $1 < 4$ より左の子 (L)。親は $\frac{1}{3}$
$\frac{1}{3}$ : $1 < 3$ より左の子 (L)。親は $\frac{1}{2}$
$\frac{1}{2}$ : $1 < 2$ より左の子 (L)。親は $\frac{1}{1}$

以上より、$\frac{1}{1}$ から $\frac{19}{44}$ へ至る経路は、上から順に L, L, L, L, L, R, R, R, L, L となる。根から10回下っているため、配置される段数は $1 + 10 = 11$ 段目である。

次に、左から何番目かを求める。ある段に並ぶ分数の「左から何番目か」は、根からの経路を2進数と対応させることで計算できる。各分岐において、左下 (L) へ進むことを $0$、右下 (R) へ進むことを $1$ とみなす。 11段目への経路 L, L, L, L, L, R, R, R, L, L は、10桁の2進数 $0000011100_{(2)}$ に対応する。これを10進数に変換すると、

$$ 0 \cdot 2^9 + \dots + 1 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 0 \cdot 2^0 $$

$$ = 16 + 8 + 4 = 28 $$

左端のノードの値を $0$ と数え始めているため、実際の順番はこの値に $1$ を足したものになる。（例えば問題文にある $\frac{3}{1}$ は R, R $\rightarrow 11_{(2)} = 3$ であり、左から $3+1=4$ 番目となっている）したがって、$28 + 1 = 29$ となり、左から29番目である。

解説

本問に登場する樹形図は「カルコフ・ブロッケン木 (Calkin-Wilf tree)」と呼ばれ、すべての正の有理数を重複なく列挙できる構造を持つ有名な題材である。 (1)の最大公約数を用いた既約性の証明は、整数問題の典型的な論法である。 (2)や(3)で「親から子へどう枝分かれするか」ではなく、「子から親へどう遡るか」という視点を持てるかがポイントとなる。分子と分母の大小関係を見るだけで、ユークリッドの互除法と同様の減算アルゴリズムが実行でき、一意に初期状態 $\frac{1}{1}$ へ還元できる。 (4)の「2進数による位置の特定」は、完全2分木におけるインデックス計算の典型手法である。Lを0、Rを1に置き換えて10進数に直す手法を知っていれば、図を描かずとも機械的かつ正確に答えを出すことができる。