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} 的所有可能取值。
第 5/6 步:结合得到严格上界
t<(n−1)s  ⟹  ts<n−1t< (n-1)s \implies \tfrac{t}{s}<n-1
详细分析

由对称性,可安排第一次操作使用初始时最右边的两个 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。