九州大学 2001年度 前期日程 第2次学力試験 整数・数列文系数学 第4問(c)

(1)

1周目の(b)では、問題文の通り $(i,j,k)=(100,n,0)$ である。$100$ は偶数なので $k$ は変わらず、$i$ は $50$、$j$ は $2n$ になる。したがって2周目の(b)では $(i,j,k)=(50,2n,0)$ である。

同様に $50$ も偶数なので、3周目の(b)では $(i,j,k)=(25,4n,0)$ である。ここで $25$ は奇数なので、(c)で $k=0+4n=4n$ となる。その後 $i=[25\mathrm{/}2]=12$、$j=8n$ となるから、4周目の(b)では $(i,j,k)=(12,8n,4n)$ である。

(2)

ある周回の(b)における値を $(i,j,k)$ とする。まず $i$ が偶数のとき、(c)では $k$ は変わらず、次の周回では $$i^{\mathrm{\prime }}={\displaystyle \frac{i}{2}},j^{\mathrm{\prime }}=2j,k^{\mathrm{\prime }}=k$$ である。したがって $$i^{\mathrm{\prime }}{j}^{\mathrm{\prime }}+k^{\mathrm{\prime }}={\displaystyle \frac{i}{2}}\cdot 2j+k=ij+k$$ である。

次に $i$ が奇数のとき、$i=2h+1$ とおく。(c)で $k$ は $k+j$ となり、次の周回では $$i^{\mathrm{\prime }}=h,j^{\mathrm{\prime }}=2j,k^{\mathrm{\prime }}=k+j$$ である。したがって $$i^{\mathrm{\prime }}{j}^{\mathrm{\prime }}+k^{\mathrm{\prime }}=h\cdot 2j+k+j=(2h+1)j+k=ij+k$$ である。

よって、どちらの場合にも次の周回で $ij+k$ は変わらない。したがって $ij+k$ は1周目から最後まで一定である。1周目では $ij+k=mn$ なので、一定値は $mn$ である。

(3)

算法が終了するのは(b)で $i=1$ となったときであり、そのとき $Ans=k+j$ と定められる。ところが $i=1$ なので $k+j=ij+k$ である。(2)より $ij+k$ は常に $mn$ に等しいから $Ans=mn$ である。

$m$ の2進表示を使う。各周回で最下位桁を読み取り、
その桁が1なら対応する $2^{s}n$ を加える算法だと説明する。
実際の値と不変量も2進表示の分解から確認する。

(1) $$100⟶50⟶25⟶12$$と半減する。$j$ は毎回2倍され、25だけが奇数なので、
3周目と4周目は$$(i,j,k)=(25,4n,0),(12,8n,4n)$$である。

(2)
$m$ の2進表示を$$m={\epsilon }_0+2{\epsilon }_1+\cdots +2^s{\epsilon }_s,{\epsilon }_{\nu }\in \{0,1\}$$とする。$r$ 周の処理後、$i$ は未処理の上位桁、
$j=2^{r}n$、$k$ は処理済みの1の桁に対応する
${\epsilon }_{0}n+\cdots +{\epsilon }_{r-1}{2}^{r-1}n$ である。
したがって常に$$ij+k=mn\mathrm{.}$$これは偶数なら桁0を捨て、奇数ならその桁の $j$ を先に加えることに対応する。

(3)
最後は最上位桁だけが残って $i=1$ となる。
そのとき$$Ans=k+j=ij+k=mn\mathrm{.}$$