整数の性質の問題

フィボナッチ数列を $F_1=1,F_2=1,F_{n+2}=F_{n+1}+F_n$ で定める。
$$F_3=2,F_4=3,F_5=5,F_6=8,F_7=13,F_8=21,F_9=34,F_{10}=55,F_{11}=89,F_{12}=144$$
である。

操作を逆にたどる。 $T(a,b)=T$ とし、操作の途中に現れる組を終わりから順に $P_0=(1,1),P_1,\dots ,P_T=(a,b)$ とする（$P_{j+1}$ に操作を 1 回行うと $P_j$ になる）。$P_{j+1}=(x,y)$ で $x>y$ なら $P_j=(x-y,y)$ であり、$x=(x-y)+y$ だから、$P_{j+1}$ は $P_j$ の一方の数を「$P_j$ の 2 数の和」に置き換えたものである（$x<y$ のときも同様）。

$P_j$ の 2 数の和を $s_j$、大きい方の数を $m_j$ とする。

• $P_{j+1}$ の 2 数は「$P_j$ の 2 数の和 $s_j$」と「$P_j$ の一方の数」なので、$s_{j+1}=s_j+(P_j\text{ の一方の数})\leqq s_j+m_j$ である。
• $j\geqq 1$ のとき、$P_j$ の 2 数は $s_{j-1}$ と「$P_{j-1}$ の一方の数（これは $s_{j-1}$ 以下）」なので、$m_j\leqq s_{j-1}$ である。

よって $j\geqq 1$ のとき
$$s_{j+1}\leqq s_j+s_{j-1}$$
が成り立つ。また $s_0=2=F_3$、$P_1$ は $(2,1)$ か $(1,2)$ なので $s_1=3=F_4$ である。$s_{j-1}\leqq F_{j+2}$、$s_j\leqq F_{j+3}$ ならば $s_{j+1}\leqq F_{j+3}+F_{j+2}=F_{j+4}$ となるから、数学的帰納法により、すべての $j$ について
$$s_j\leqq F_{j+3}$$
である。

下からの評価. $a+b=100$ のとき $s_T=100$ である。もし $T\leqq 8$ なら $100=s_T\leqq F_{T+3}\leqq F_{11}=89$ となり矛盾する。よって $T(a,b)\geqq 9$ である。

9 回になる例. $(a,b)=(61,39)$ は $61$ と $39=3\cdot 13$ が互いに素で $a+b=100$ を満たし、
$$(61,39)\to (22,39)\to (22,17)\to (5,17)\to (5,12)\to (5,7)\to (5,2)\to (3,2)\to (1,2)\to (1,1)$$
となるので $T(61,39)=9$ である。

以上より、求める最小値は $9$ である。

操作を逆にたどる。$(1,1)$ から出発して、「$(x,y)\to (x+y,y)$ または $(x,x+y)$」（大きい方に小さい方を足す）を $n$ 回行って得られる組を考える。

【下からの評価】$(1,1)$ から $n$ 回の逆操作の後の組の大きい方の数を $M_n$、和を $s_n$ とおく。$n=0$ で $M_0=1,s_0=2$。逆操作では新しい大きい方は（元の和）$=s_n$ 以下であり、元の大きい方 $M_n$ と小さい方 $m_n$ に対し、新しい和は $s_n+M_n$ または $s_n+m_n$ なので $s_{n+1}\le s_n+M_n$。また、新しい大きい方は $s_n$ 以下。これより、フィボナッチ数 $F_1=F_2=1,F_{k+1}=F_k+F_{k-1}$ を使って、帰納法で $M_n\le F_{n+2}$、$s_n\le F_{n+3}$ が示せる（$n=0$: $M_0=1=F_2$, $s_0=2=F_3$。$n$ で成り立つとき、新しい組の大きい方は $M_n+m_n\le$ 元の和かつ、小さい方でない側は $M_n$ で、$m_n\le M_{n-1}\le F_{n+1}$ より $M_{n+1}\le M_n+m_n\le F_{n+2}+F_{n+1}=F_{n+3}$ であり、$s_{n+1}\le s_n+M_n\le F_{n+3}+F_{n+2}=F_{n+4}$）。

$n=8$ のとき $s_8\le F_{11}=89<100$ なので、$a+b=100$ となる組は $8$ 回以下の操作では $(1,1)$ に到達できない。よって $T(a,b)\ge 9$。

【実現】$(a,b)=(39,61)$（$\gcd =1$、和 $100$）を考える。
$(39,61)\to (39,22)\to (17,22)\to (17,5)\to (12,5)\to (7,5)\to (2,5)\to (2,3)\to (2,1)\to (1,1)$。
矢印は $9$ 本なので $T(39,61)=9$。

以上より最小値は $9$。
（確かめ: 逆にたどると $(1,1)\to (2,1)\to (2,3)\to (2,5)\to (7,5)\to (12,5)\to (17,5)\to (17,22)\to (39,22)\to (39,61)$ で和 $100$。）