MathLabs

第5問

n≥3n\ge3 を固定された整数とする。黒板に数 11 が nn 個書かれている。黒板の下には最初は空の2つのバケツがある。1回の操作は、2つの数 aa と bb を消して、代わりに 11 と a+ba+b を書き、さらに1個目のバケツに石を1個、2個目のバケツに gcd⁡(a,b)\gcd(a,b) 個の石を加えることからなる。有限回の操作の後、1個目のバケツに ss 個、2個目のバケツに tt 個の石があり、ss、tt は正整数であるとする。比 ts\dfrac{t}{s} のとりうるすべての値を求めよ。
ステップ 2/6: バケツ1は操作回数を数える;比は少なくとも1
s=p−n,p=sum of the numbers on the board;t≥ss=p-n,\quad p=\text{sum of the numbers on the board};\qquad t\ge s
詳しい解説

各操作でバケツ1にはちょうど1個の石が加わるので、ss は行った操作の回数に等しく、pp を黒板上の nn 個の数の和とすると各操作で pp はちょうど 11 増える(a+ba+b を消して 1+(a+b)1+(a+b) を書き戻すため)ので p=n+sp=n+s となる。各操作で gcd⁡(a,b)≥1\gcd(a,b)\ge1 なので、バケツ2は各操作でバケツ1以上の石を得るから t≥st\ge s、すなわち t/s≥1t/s\ge1 である。