数理論理学・集合論の問題

解釈　葉を $0$、左右の部分木の番号が $a,b$ である節点を $J(a,b)+1$ で表すと、これは（全二分木）全体と $\mathbb{N}$ の間の全単射なゲーデル数付けになる。$n+1$ が表す木の左右の部分木は $K(n),L(n)$ が表す木なので、$f(n)$ は番号 $n$ の木の葉の個数である。したがって「葉が $9$ 個の木のうち番号が最小のもの」を求めればよい。

$J$ の大小関係　$s=x+y$ とおくと $J(x,y)=\frac{s(s+1)}{2}+y$ で、$0\le y\le s$ なので $J$ の値は $\frac{s(s+1)}{2}$ 以上 $\frac{s(s+1)}{2}+s<\frac{(s+1)(s+2)}{2}$ 以下。よって $J(x,y)$ は、まず $s=x+y$ が小さいほど小さく、$s$ が同じなら $y$ が小さいほど小さい。

$K,L$ の求め方　$m$ に対し $\frac{w(w+1)}{2}\le m$ となる最大の $w$ をとり、$L(m)=m-\frac{w(w+1)}{2}$、$K(m)=w-L(m)$。

$f(0),\dots ,f(12)$ の計算　$f(n+1)=f(K(n))+f(L(n))$ を順に計算する。

まとめると $f(0)=1$, $f(1)=2$, $f(2)=f(3)=3$, $f(4)=f(5)=f(6)=f(7)=f(10)=4$, $f(8)=f(9)=f(11)=f(12)=5$ である。

$f(n)\ge 6$ となる $n$ は $13$ 以上　$n\ge 1$ のとき $f(n)=f(a)+f(b)$（$n-1=J(a,b)$）。$f(a)+f(b)\ge 6$ となるのは、たとえば $f(a)=f(b)=3$（$a,b\ge 2$ で $a+b\ge 4$, $y=b\ge 2$）などで、最小は $J(2,2)=12$、つまり $n=13$。実際、上の表の $n\le 12$ ではすべて $f(n)\le 5$ である。

$f(n)=9$ となる最小の $n$　$n\ge 1$ で $n-1=J(a,b)$、$f(a)+f(b)=9$ となる $(a,b)$ のうち $J(a,b)$ が最小のものを探す。$f(a),f(b)$ の分け方ごとに、$f$ の値をとる最小の番号（$f=1$ は $0$、$f=2$ は $1$、$f=3$ は $2$、$f=4$ は $4$、$f=5$ は $8$、$f\ge 6$ は $13$ 以上）から $a+b$ の下限を見ると
- $\{f(a),f(b)\}=\{4,5\}$：$a+b\ge 4+8=12$
- $\{3,6\}$：$a+b\ge 2+13=15$
- $\{2,7\},\{1,8\}$：一方の $f$ が $7$ 以上なので、その番号は $13$ より大きく $a+b>12$（実際には $f(13)=6$ で、$f\ge 7$ の最小番号は $24$ である）

よって $a+b\ge 12$ で、$a+b=12$ となりうるのは $\{4,5\}$ の分け方だけである。$a+b=12$ のもとで $y=b$ を小さい順に調べる（$a=12-b$）:
- $b=0$：$f(12)+f(0)=5+1=6$
- $b=1$：$f(11)+f(1)=5+2=7$
- $b=2$：$f(10)+f(2)=4+3=7$
- $b=3$：$f(9)+f(3)=5+3=8$
- $b=4$：$f(8)+f(4)=5+4=9$ ✓

したがって最小は $(a,b)=(8,4)$ で、$J(8,4)=\frac{12\cdot 13}{2}+4=82$、$n=83$。

検算　$n-1=82$：$\frac{12\cdot 13}{2}=78\le 82<91$ より $w=12$, $L(82)=4$, $K(82)=8$。$f(83)=f(8)+f(4)=5+4=9$。

よって求める最小の $n$ は $83$ である。

$J^{-1}(n)$ は、$s(s+1)/2\le n<(s+1)(s+2)/2$ となる $s$ を取り、$L(n)=n-s(s+1)/2$、$K(n)=s-L(n)$ で得られる。$f(0)=1$、$f(n+1)=f(K(n))+f(L(n))$ を順に計算する（$n\mapsto (K,L)$ と $f(n+1)$）。

$n=0$: $(0,0)$, $f(1)=2$。
$n=1$: $(1,0)$, $f(2)=f(1)+f(0)=3$。
$n=2$: $(0,1)$, $f(3)=3$。
$n=3$: $(2,0)$, $f(4)=4$。$n=4$: $(1,1)$, $f(5)=4$。$n=5$: $(0,2)$, $f(6)=4$。
$n=6$: $(3,0)$, $f(7)=4$。$n=7$: $(2,1)$, $f(8)=3+2=5$。$n=8$: $(1,2)$, $f(9)=5$。$n=9$: $(0,3)$, $f(10)=4$。
$n=\mathrm{10..14}$: $f(\mathrm{11..15})=5,5,6,5,5$。
$n=\mathrm{15..20}$: $f(\mathrm{16..21})=5,6,6,6,6,5$。
$n=\mathrm{21..27}$: $f(\mathrm{22..28})=5,6,7,6,7,6,5$。
$n=\mathrm{28..35}$: $f(\mathrm{29..36})=5,6,7,7,7,7,6,5$。
$n=\mathrm{36..44}$: $f(\mathrm{37..45})=6,6,7,7,8,7,7,6,6$。
$n=\mathrm{45..54}$: $f(\mathrm{46..55})=6,7,7,7,8,8,7,7,7,6$。
$n=\mathrm{55..65}$: $f(\mathrm{56..66})=5,7,8,7,8,8,8,7,8,7,5$。
$n=\mathrm{66..77}$: $f(\mathrm{67..78})=6,6,8,8,8,8,8,8,8,8,6,6$。
$n=78$: $(12,0)$, $f(79)=f(12)+f(0)=6$。$n=79$: $(11,1)$, $f(80)=f(11)+f(1)=7$。$n=80$: $(10,2)$, $f(81)=f(10)+f(2)=7$。$n=81$: $(9,3)$, $f(82)=f(9)+f(3)=8$。
$n=82$: $s=12$, $L=82-78=4$, $K=8$。$f(83)=f(8)+f(4)=5+4=9$。

$f(1),\dots ,f(82)$ はすべて 8 以下で、$f(0)=1$ なので、$f(n)=9$ をみたす最小の $n$ は 83。

検算: $J(8,4)=\frac{12\cdot 13}{2}+4=82$ で、$K(82)=8,L(82)=4$ と一致。