大阪大学理系 2019年前期 問題4
$右の図は、\cfrac{1}{1}\ から始めて分数 \ \cfrac{p}{q}\ の左下に分数 \ \cfrac{p}{p+q},右下に分数 \ \cfrac{p+q}{q}\ を配置するという規則でできた$
$樹形図の一部である。このとき以下の問いに答えよ。$
$\hspace{10em}$ 
$(1)\ \ この樹形図に現れる分数はすべて既約分数であることを示せ。ただし整数 \ \cfrac{n}{1}\ は既約分数とみなす。$
$(2)\ \ すべての正の有理数がこの樹形図に現れることを示せ。$
$(3)\ \ この樹形図に現れる有理数はすべて異なることを示せ。$
$(4)\ \ \cfrac{19}{44}\ はこの樹形図の上から何段目の左から何番目に配置されるかを答えよ。たとえば、\cfrac{3}{1}\ は上から$
$\hspace{2em}3段目の左から4番目である。$
$かなりユニークな問題で、どう手をつけたらいいかすぐには思いつかない問題です。私なりの考えを載せますが、$
$出題者の意図した解答かどうかはわかりません。正解率はどの位と予想したのでしょうか。$
(1)
$定理 \qquad p,\ q\ が整数のとき、(p,\ q)=1 \ ならば \ (p,\ p+q)=1 \qquad ただし \ (p,\ q)\ は \ p,\ q\ の最大公約数である。$
$(証明)$
$(p,\ p+q)=d \ \ (d\ は整数)\ とおくと \ \ p=ld,\quad p+q=md \ \ (l,\ mは整数)\ \ とおけるから$
$ld+q=md \ \ より \ \ q=(m-l)d$
$よって、d\ は \ q\ の約数,\quad d\ は \ p\ の約数だから \ d\ は \ p,\ q\ の公約数である。$
$ところが、(p,\ q)=1 \ \ だから \ \ d=1 \ \ となって\ \ (p,\ p+q)=1$
$この定理から、\cfrac{p}{q}\ が既約分数ならば \ \cfrac{p}{p+q}\ も既約分数であることがわかる。$
$全く同様にして、\cfrac{p}{q}\ が既約分数ならば \ \cfrac{p+q}{q}\ も既約分数となることが示される。$
$\qquad なお、(\ \ (a,b)=(a,ka+b)\ となることは$(最大公約数の性質$を参照してください。)$
(2)
$この樹形図から任意の有理数 \ \cfrac{m}{n}\ をとる。この有理数の1つ前は$
(i)$\ \ m < n \ \ のときは \quad 右上に有理数 \cfrac{m}{n-m}\ \ がある。$
(ii)$\ \ m > n \ \ のときは \quad 左上に有理数 \cfrac{m-n}{n}\ \ がある。$
$このように、1つ前にもどるとき$
(i)$\ \ 分子 < 分母 \quad のときは \quad \cfrac{分子}{分母-分子}$
(ii)$\ \ 分子 > 分母 \quad のときは \quad \cfrac{分子-分母}{分母}$
$となって、分子または分母は小さくなる。$
$この1つ前にもどるという操作は分子、分母がともに \ 1\ になるまで続けられ、最後は \ \cfrac{1}{1}\ で止まる。$
$したがって、\cfrac{1}{1}\ から始めて、逆向きにこのルートをたどればただ \ 1\ 通りに \ \cfrac{m}{n}\ にたどり着く。$
$このようにして、任意の有理数をつくることができる。$
(3)
$(2)でみたように、\cfrac{1}{1}\ から \ \cfrac{m}{n}\ に至るルートはただ \ 1\ 通りであるから$
$ルート \ \ \longleftrightarrow \cfrac{m}{n} \quad は \ 1\ 対 \ 1\ 対応である。$
$したがって、ルートが同じならば同じ有理数、ルートが異なれば異なる有理数が得られる。$
(4)
$\cfrac{19}{44}\ \ から逆にルートをたどっていくと、\cfrac{1}{6}\ \ にたどりつく。$
$\cfrac{1}{6}\ \ は6段目の左から1番目であるから、これを \ (6,1)\ と書くことにする。$
$\quad \cfrac{1}{6} \quad \longrightarrow \quad \cfrac{7}{6}\ \ へは右下への移動だから、左から2番目$
$\quad \cfrac{7}{6} \quad \longrightarrow \quad \cfrac{13}{6}\ \ へは右下への移動ですが、左から順に \ \cfrac{1}{8},\ \ \cfrac{8}{7}, \ \ \cfrac{7}{13}\ \ が入るから\ \ 2 \times 1+2=4\ 番目$
$\quad \cfrac{13}{6} \quad \longrightarrow \quad \cfrac{19}{6}\ \ へは右下への移動で、2 \times (4-1)+2=8\ 番目$
$\quad \cfrac{19}{6} \quad \longrightarrow \quad \cfrac{19}{25}\ \ へは左下への移動で、2 \times (8-1)+1=15\ 番目$
$\quad \cfrac{19}{25} \quad \longrightarrow \quad \cfrac{19}{44}\ \ へは左下への移動で、2 \times (15-1)+1=29\ 番目$
$まとめると$
$\hspace{3em} \cfrac{19}{44} \quad \longleftarrow \quad \cfrac{19}{25} \quad \longleftarrow \quad \cfrac{19}{6} \quad \longleftarrow \quad \cfrac{13}{6} \quad \longleftarrow \quad \cfrac{7}{6} \quad \longleftarrow \quad \cfrac{1}{6}$
$\hspace{3em} (11,29) \hspace{2em}(10,15) \hspace{2em}(9,8) \hspace{3em}(8,4) \hspace{3em}(7,2) \hspace{3em}(6,1)$
$\quad \cfrac{19}{44} \ \ は上から \ 11\ 段目の左から \ 29\ 番目に配置される。$
メインメニュー に戻る