MathLabs

第5题

设 n≥3n\ge3 为固定整数。黑板上写有 nn 个数 11。黑板下方有两个初始为空的桶。一次操作是擦去其中两个数 aa 与 bb，用 11 和 a+ba+b 替换它们，然后往第一个桶中加入一颗石子，往第二个桶中加入 gcd⁡(a,b)\gcd(a,b) 颗石子。经过有限次操作后，第一个桶中有 ss 颗石子，第二个桶中有 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，仅需一次操作即得 t=s=1t=s=1。对一般有理数 p/q∈(1,n−1)p/q\in(1,n-1)：对 nn 归纳可知，对任意正整数 aa，可将黑板变为 n−1n-1 个 11 与一个 an−1a^{n-1}，用去 s=an−1−1s=a^{n-1}-1 次操作，第二个桶得到 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 规模的构造应用两次得到两个 an−2a^{n-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} 为整数，且当 aa 充分大时该分子为正（因为 q(n−1)>pq(n-1)>p）；取这样充分大的 aa 即得 b>0b>0 并实现比值 p/qp/q。因此 [1,n−1)[1,n-1) 内的每个有理数都能取到。