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} 的所有可能取值。
第 2/6 步：第一个桶记录移动次数；比值至少为 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
详细分析

每次操作恰好往第一个桶加入一颗石子，故 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，第二个桶每次获得的石子数不少于第一个桶，故 t≥st\ge s，即 t/s≥1t/s\ge1。