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} のとりうるすべての値を求めよ。
ステップ 6/6: [1,n-1) 内のすべての有理数を実現する
前のステップ次のステップ
t=an−2(a−1)(n−1),s=an−1−1,t+bs+b→pqt=a^{n-2}(a-1)(n-1),\quad s=a^{n-1}-1,\quad \frac{t+b}{s+b}\to \frac{p}{q}
詳しい解説

t/s=1t/s=1 については、1回の操作だけで t=s=1t=s=1 が得られる。一般の有理数 p/q∈(1,n−1)p/q\in(1,n-1) については、nn に関する帰納法により、任意の正整数 aa に対して盤面を n−1n-1 個の 11 と1個の an−1a^{n-1} にでき、そのとき s=an−1−1s=a^{n-1}-1 回の操作と、バケツ2に t=an−2(a−1)(n−1)t=a^{n-2}(a-1)(n-1) 個の石を得る（基本ケース n=2n=2：11 と成長する数を a−1a-1 回繰り返し組み合わせると s=t=a−1s=t=a-1；帰納段階ではサイズ n−1n-1 の構成を2回適用して an−2a^{n-2} を2つ作り、それらを合体させる）。その後、11 と大きい数をさらに bb 回組み合わせると両方のバケツに bb が加わり、比 an−2(a−1)(n−1)+ban−1−1+b\dfrac{a^{n-2}(a-1)(n-1)+b}{a^{n-1}-1+b} が得られる。a≡1(modp−q)a\equiv1\pmod{p-q} を選ぶと b=q an−2(a−1)(n−1)−p(an−1−1)p−qb=\dfrac{q\,a^{n-2}(a-1)(n-1)-p(a^{n-1}-1)}{p-q} は整数になり、q(n−1)>pq(n-1)>p なので aa が十分大きければこの分子は正になる；そのような大きい aa をとれば b>0b>0 となり比 p/qp/q が実現される。よって [1,n−1)[1,n-1) 内のすべての有理数が現れる。