第3問

正五角形の各頂点に整数を割り当て、5数の総和を正とする。連続する3頂点の数が

x,y,z

で

y<0

のとき、それらをそれぞれ

x+y,-y,z+y

に置き換える。負の数がある限りこの操作を繰り返す。この手続きは必ず有限回で終了するか。

ステップ 4/4: 終了を導く

ざっくり言うと

合法な操作は非負整数を必ず厳密に下げるので、操作回数は有限である。

2Sx_4<0

詳しい解説

$S>0$ かつ合法な操作では $x_4<0$ なので $f_{\rm new}-f_{\rm old}=2Sx_4<0$ 。無限に続けば非負整数の無限厳密減少列ができて矛盾する。よって手続きは必ず終了する。