OMC186(D) - 不変量を作る

不変量を作って解く方法を解説する．

アイディア

$a_n$と$b_n$の（大きい方）/（小さい方）の値を$k_n$とする．$k_n$は遷移によってあまり変わらないので，$k_n$を利用して不変量を作るのが良さそうである．そこで小さい数で$k_n$の遷移を観察しよう．例えば $$(32,5)\to (3,19)\to (13,2)\to (1,6)$$ という遷移の場合，$k_n$は $$6.4\to 6.33\dots\to 6.5\to 6$$ となり，$6$から$6.5$の間を動く．また $$(7,32)\to (23,5)\to (2,9)\to (5,1)$$ という遷移の場合，$k_n$は $$4.57\dots\to 4.6\to 4.5\to 5$$ となり，$4.5$から$5$の間を動く． このような例から，$k_n$以下の最大の0.5の倍数が不変であることが予想できる．ただし一つ目の例の$6.5$は$6.4999\dots$と解釈する（つまり$6.5$より小さいかのように扱う）必要があり，二つ目の例の$5$は$4.9999\dots$と解釈する（つまり$5$より小さいかのように扱う）必要がある．このような発想で不変量を作ると以下のようになる．

なお，ここまでの考察をもとに正しく不変量を予想できれば，それが不変量であることを証明せずとも答えを導くことができる．

解答

実数$x$に対し，$x$以下の最大の$0.5$の倍数を$\langle x\rangle$で表すことにする． 定義から$a_n$と$b_n$は常に互いに素であり，したがって$a_n=b_n$となるのは$(a_n,b_n)=(1,1)$の場合のみである．また，$(a_n,b_n)\neq (1,1)$ならば$a_{n-1}-b_{n-1}$と$a_n-b_n$の符号は異なる（公式解説参照）．ここで十分小さい正の実数$\varepsilon$（例えば$\varepsilon=2^{-100000000000}$）を取り， $$P_n=\begin{cases}\langle k_n-\varepsilon\rangle&(a_n\gt b_n)\\ \langle k_n+\varepsilon\rangle&(a_n\leq b_n)\end{cases}$$ と定める．ただし$k_n=\max\{a_n,b_n\}/\min\{a_n,b_n\}$である．このとき$P_{n-1}=P_n$が成り立つことを示そう．

• $a_{n-1}\gt b_{n-1}$の場合，前述のように$a_n\leq b_n$であり，$(a_{n-1},b_{n-1})$が終状態でないことから$b_{n-1}\geq 2$である．これらと$a_{n-1}a_n-b_{n-1}b_n=1$を合わせると $$\dfrac{b_n}{a_n}\lt\dfrac{a_{n-1}}{b_{n-1}}\leq\dfrac{b_n+0.5}{a_n}$$ が得られる．したがって$k_n+\varepsilon, k_{n-1}-\varepsilon$はいずれも$\dfrac{b_n}{a_n}\lt x\lt \dfrac{b_n+0.5}{a_n}$の範囲にあるが，この範囲には$\dfrac{0.5}{a_n}$の倍数が存在しないので，特に0.5の倍数は存在しない．よってこれらに対する$\langle{x}\rangle$の値は一致する．
• $a_{n-1}\lt b_{n-1}$の場合，$(a_n,b_n)\neq(1,1)$となるため$a_n\gt b_n$であり，$(a_{n-1},b_{n-1})$が終状態でないことから$a_{n-1}\geq 2$である．これらと$a_{n-1}a_n-b_{n-1}b_n=1$を合わせると $$\dfrac{a_n-0.5}{b_n}\leq\dfrac{b_{n-1}}{a_{n-1}}\lt\dfrac{a_n}{b_n}$$ が得られる．したがって$k_{n-1}+\varepsilon, k_n-\varepsilon$はいずれも$\dfrac{a_n-0.5}{b_n}\lt x\lt \dfrac{a_n}{b_n}$の範囲にあるが，この範囲には$\dfrac{0.5}{b_n}$の倍数が存在しないので，特に0.5の倍数は存在しない．よってこれらに対する$\langle{x}\rangle$の値は一致する．

以上より$P_n$の値は$n$によらず一定である．終状態$(a_N,b_N)$における値は $$\begin{aligned}&(a_N,b_N)=(m,1),m\gt1\implies P_N=m-0.5,\\ &(a_N,b_N)=(1,m),m\geq 1\implies P_N=m\end{aligned}$$ となり全て異なるため，終状態としてあり得る組の総数は，$P_0$としてあり得る値の総数に等しい．初期状態$(a_0,b_0)$における値は $$\begin{aligned}&(a_0,b_0)=(2^{25},1),(1,2^{25})\implies P_0=2^{25}-0.5,2^{25},\\ &(a_0,b_0)=(2^{25},x),(x,2^{25})\implies P_0=\langle 2^{25}/x\rangle=\dfrac{1}{2}\lfloor 2^{26}/x\rfloor\quad(x=3,5,7,\dots,2^{25}-1)\end{aligned}$$ となるため，$x=3,5,7,\dots,2^{25}-1$に対する$\lfloor 2^{26}/x\rfloor$としてあり得る値の総数に$2$を加えたものが答えである．あとは公式解説と同様である．