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} のとりうるすべての値を求めよ。
ステップ 5/6: 組み合わせて厳密な上界を得る
t<(n−1)s  ⟹  ts<n−1t< (n-1)s \implies \tfrac{t}{s}<n-1
詳しい解説

対称性により、最初の操作は初めの右端2個の 11 を使うように配置してよい。直後には s=t=1s=t=1 かつ q=q0+(n−1)=(n+2)(n−1)2q=q_0+(n-1)=\tfrac{(n+2)(n-1)}2 である。q−tq-t は減少しないので、その後の任意の状態で q≥t+(n+2)(n−1)2−1q\ge t+\tfrac{(n+2)(n-1)}2-1。これと q≤(n−1)s+n(n−1)2q\le(n-1)s+\tfrac{n(n-1)}2 を合わせると、n≥3n\ge3 より t≤(n−1)s−(n−2)<(n−1)st\le(n-1)s-(n-2)<(n-1)s となる。t≥st\ge s と合わせて t/s∈[1,n−1)∩Qt/s\in[1,n-1)\cap\mathbb Q を得る。