SLP2018 Cうめ - Ktya’s blog

SLP 2018 C6

概要

aとbを異なる正整数とする。何も数字が描かれていない黒板に対して以下の操作を無限回行う。
①　黒板に同じ数字が書かれているときどちらかをa増やし、もう片方をb増やす。
②　①ができないとき、新しく0を二つ書く。
ここで、どのように①の操作を行っても②の操作を行う回数は必ず有限回になることを示せ。

以下後日更新

証明

g=gcd(a,b)としたときに、全ての数をgで割ることでg=1として一般性を失わない。
①の操作を有限回、②の操作をN+1回行った直後の状態を考える。
$f(N,x)$ で本状態に至るまでに黒板にxが書かれた回数をあらわすことにする。xが負の時は0として、第二変数は整数全体で定義する。黒板にxが書かれるためにはその前にx-aが二個もしくはx-bが二個書かれている必要があり、一度x-aのペアを使用すると片方はx-a+bとなり、操作の方法より、書かれている数が減ることはないため、以下の式が成立する。(式Aとする)
$f(N,x)=\lfloor\frac{f(N,x-a)}{2}\rfloor +\lfloor \frac{f(N,x-b)}{2}\rfloor$
$f(N,0)=2N$ に注意する。

次を示す。
「k,Mを $k\leq M$ を満たす整数とする。特にMは正整数とする。 $f(N,ka+(M-k)b)\geq \frac{2N}{2^M}-2$ が成立する。」
証明：Mに関する帰納法を行う。M=0の時は $f(N,0)=2*N$ になので従う。
前述の式Aにより、M>0の時、
$f(N,ka+(M-k)b)\geq \lfloor\frac{f(N,(k-1)a+(M-k)b)}{2}\rfloor +\lfloor \frac{f(N,ka+(M-k-1)b)}{2}\rfloor$

となり、帰納法から従う。

本不等式により、 $N\geq 2^M$ のときに $f(N,ka+(M-k)b)\geq 2$ が成立する。
また有名な事実として、(aとbは互いに素としているので)ab-a-bより大きい数はna+mb(n,mは0以上の整数)であらわすことができる。
これにより、y=ab-a-bとして、 $y+1,y+1,\ldots, y+a+b$ はna+mb(n,mは0以上の整数)という形で表すことができる。 $y+k = n_{k}a+m_{k}b$ と表せるとして、 $N=2^{\max{n_k+m_k}}$ とすれば、 $f(N,x)\geq 2$ がx=y+1~y+a+bで成立する。一方で式Aを繰り返し用いると、yより大きな数全てについて $f(N,x)\geq 2$ が成立することが得られるが、操作①も操作②も有限回であることに矛盾する。
以上より、 $N　\leq 2^{\max{n_k+m_k}}$ すなわちNが有限であることが示される。