第2問

$a_i\ge2^m$ ならば、半分にすると因子 $2$ が一つ取り除かれるので $b_{i+1}=b_i$。$a_i<2^m$ ならば $a_{i+1}=b_i^22^{2c_i}+2^m$；$2^{\min(2c_i,m)}$ を括り出すと、$2c_i\ne m$ のとき奇数部分は $b_i^22^{|2c_i-m|}+1$ となり、これは $b_i^2\ge b_i$ を超える；$2c_i=m$ のときは $(b_i^2+1)/2$（$b_i$ が奇数のとき $b_i^2\equiv1\pmod8$ なので奇数）となり、$(b_i-1)^2\ge0$ より $b_{i+1}\ge b_i$ を満たし、等号は $b_i=1$ のときに限る。よって $b_i$ は決して減らず、この唯一の境界の場合を除き小さい方の規則を使う各ステップで真に増加する。