2019年(平成31年)大阪大学-数学(理系)[4] - [別館]球面倶楽部零八式markIISR

[4] 下の図は、 $\dfrac{1}{1}$ から始めて分数 $\dfrac{p}{q}$ の左下に分数 $\dfrac{p}{p+q}$ ，右下に分数 $\dfrac{p+q}{q}$ を配置するという規則でできた樹形図の一部である．このとき以下の問いに答えよ．

(1) この樹形図に現れる分数はすべて既約分数であることを示せ．ただし整数 $\dfrac{n}{1}$ は既約分数とみなす．

(2) すべての正の有理数がこの樹形図に現れることを示せ．

(3) この樹形図に現れる有理数はすべて異なることを示せ．

(4) $\dfrac{19}{44}$ はこの樹形図の上から何段目の左から何番目に配置されるか答えよ．たとえば， $\dfrac{3}{1}$ は上から3段目の左から4番目である．

（図省略）

本問のテーマ

カルキン・ウィルフ(Calkin-Wilf) ツリー(2022.09.19)

2019.02.27記

有理数が可付番であることの証明のために正の有理数を一列に並べるとき、分母と分子の和が小さい順番に並べたり、二次元格子点を原点から螺旋状に並べたりするが、これらにおいて、可約分数を除いて並べるため、どの分数が何番目に来るかを知るのはちょっと面倒になる。しかし、この並べ方だと正の有理数がちょうど一度だけあらわれるので無駄がない並べ方になっているのが面白い。初めて知ったので今後何かの機会に使いたい。

[解答]
(1) ユークリッドの互除法から、 $p+q$ と $p$ の最大公約数、及び $p+q$ と $q$ の最大公約数はそれぞれ $p$ と $q$ の最大公約数に等しいので、帰納的に互いに素になる。よって既約分数。

(2) $\dfrac{p}{q}$ （ $p$ と $p$ は互いに素）において、まず $p\gt q$ の場合について考える。 $p=sq+r$ （ $p$ を $q$ で割った商を $s(\gt 1)$ 、余りを $r(0\lt r\lt q)$ とする。
$p$ と $q$ は互いに素なので $r\neq 0$ ）もし、 $\dfrac{r}{q}$ が樹形図に登場するならば、その $s$ 段下に $\dfrac{p}{q}$ が登場する。

次に $p\lt q$ の場合について考える。 $q=sp+r$ （ $q$ を $p$ で割った商を $u(\gt 1)$ 、余りを $t(0\lt t\lt p)$ とする。 $p$ と $p$ は互いに素なので $t\neq 0$ ）
もし、 $\dfrac{p}{t}$ が樹形図に登場するならば、その $s$ 段下に $\dfrac{p}{q}$ が登場する。

この操作で分母と分子の和が小さくなっていることに注意しておく。

これを繰り返したとき、分母と分子の和は単調減少し、 $p$ と $q$ は互いに素だから、やがて $\dfrac{1}{1}$ に到達する。つまり、すべての正の有理数から $\dfrac{1}{1}$ に到達する道筋があるので、すべての正の有理数はこの樹形図に登場する。

(3)分子が分母より大きいときは、商の数だけ上の段に登るとき樹形図で左上に進むことになり、分子が分母より小さいときは、商の数だけ上の段に登るとき樹形図で右上に進むことになる。
つまり、一つの有理数が $\dfrac{1}{1}$ に到達する戻り方は1通りしかないので、同じ有理数は樹形図の中には登場しない。

(4) $44=2\times 19+6$ , $19=3\times 6+1$ , $6=6\times 1$ であるから、商の合計は $2+3+6=11$ だから $11$ 段目。
ここに到達するとき、 $\dfrac{1}{1}\to\dfrac{1}{6}\to\dfrac{19}{6}\to\dfrac{19}{44}$ と進む。つまり左下に $6-1=5$ 、右下に $3$ 、左下に $2$ だけ進む。左下、右下に進むことをそれぞれ $0,1$ で表し、
それを「左から並べ」た2進数を考えると、それは $0000011100_{(2)}=28_{(10)}$ となる。左端が0番目でなく1番目と数えるので $28+1=29$ 番目になる。

このアルゴリズムだと、 $\dfrac{23}{87}$ がどこに登場するかを知りたければ、 $87=3\times 23+18$ ， $23=1\times 18+5$ ， $18=3\times 5+3$ ， $5=1\times 3+2$ ， $3=1\times 2+1$ ， $2=2\times 1$ であるから、 $3+1+3+1+1+2=11$ 段目にあり、左から $1010001000_{(2)}+1=648$ 番目であることがわかる。

2022.09.19記
これは Calkin-Wilf tree と呼ぶらしい．
Calkin–Wilf tree - Wikipedia

色々調べると，色々な人が解説を書いている．
honyajitsu.cocolog-nifty.com
mysandbox.hatenadiary.com

こういう文献もある．
The Calkin-Wilf tree of a quadratic surd(arXiv)
The Calkin-Wilf Tree and Its Various Properties (pdf)

ついでに

Consider the function

f(x) = 1 / ( ⌊x⌋ + 1 − {x} )

and the sequence of numbers

0, f(0), −f(0), f(f(0)), −f(f(0)), f(f(f(0))), −f(f(f(0))), ...

Congratulations, you've just listed every rational number exactly once! pic.twitter.com/NRlNnx49Ql
— Tamás Görbe (@TamasGorbe) 2022年9月18日

という tweet があったが，これは
Calkin–Wilf tree - Wikipedia
の Breadth first raversal というところにある

Calkin–Wilf sequence can also be generated directly by the formula
$q_{i+1}=\dfrac{1}{2\lfloor q_i\rfloor -q_i+1}$
where $q_i$ denotes the $i$ th number in the sequence, starting from $q_i=1$ , and $\lfloor q_i \rfloor$ represents the integral part.

と同じ漸化式．ここにある話は，上記解答(4)のアルゴリズムに相当している．これに関しては天書の証明に乗っているらしい．昔読んだから普通に解けたのかも知れないので，確認しておく．

と思ったが，このアルゴリズムを見ると $\dfrac{19}{44}$ の連分数表示が
$\dfrac{19}{44}=\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{6}}}$
だから，連分数表示から数列の何番目かわかる方式になっているので，この漸化式を理解するには連分数表示を使うと良いのだな(これは wikipedia にも軽く書いてある)．このあたりは
スターンの$2$原子数列(5-表) ～カルキン・ウィルフ・ツリーと既約分数～: ほにゃらら実験室
に割と詳しく書いてある．

2022.09.20記
天書の証明(原著第6版)を確認した．

天書の証明原書6版

作者:蟹江幸博
丸善出版

Amazon

「第19章集合，関数，連続体仮説」(p.145)にカルキン・ウィルフ(Calkin-Wilf) ツリーが書いてあり，
Calkin–Wilf sequence can also be generated directly by the formula
$q_{i+1}=\dfrac{1}{2\lfloor q_i\rfloor -q_i+1}$
where $q_i$ denotes the $i$ th number in the sequence, starting from $q_i=1$ , and $\lfloor q_i \rfloor$ represents the integral part.
の説明も書いてある．説明を知りたければ天書の証明(原著第6版)を確認して欲しい．