MathLabs

Problem 5

Let n≥3n\ge3 be a fixed integer. The number 11 is written nn times on a blackboard. Below the blackboard, there are two buckets that are initially empty. A move consists of erasing two of the numbers aa and bb, replacing them with the numbers 11 and a+ba+b, then adding one stone to the first bucket and gcd⁡(a,b)\gcd(a,b) stones to the second bucket. After some finite number of moves, there are ss stones in the first bucket and tt stones in the second bucket, where ss and tt are positive integers. Find all possible values of the ratio ts\dfrac{t}{s}.
Step 6 of 6: Achieving every rational in [1,n-1)
Previous stepNext step
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}
Detailed analysis

For t/s=1t/s=1, a single move already gives t=s=1t=s=1. For a general rational p/q∈(1,n−1)p/q\in(1,n-1): by induction on nn, for any positive integer aa one can reach a board with n−1n-1 copies of 11 and one copy of an−1a^{n-1} using s=an−1−1s=a^{n-1}-1 moves and t=an−2(a−1)(n−1)t=a^{n-2}(a-1)(n-1) stones in bucket 2 (base case n=2n=2: repeatedly combining 11 with the growing number a−1a-1 times gives s=t=a−1s=t=a-1; the inductive step applies the size-n−1n-1 construction to build an−2a^{n-2} twice and then merges the two copies). Afterwards, repeatedly combining 11 with the large number bb more times adds bb to both buckets, giving ratio an−2(a−1)(n−1)+ban−1−1+b\dfrac{a^{n-2}(a-1)(n-1)+b}{a^{n-1}-1+b}. Choosing a≡1(modp−q)a\equiv1\pmod{p-q} makes 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} an integer, and this numerator is positive once aa is large enough because q(n−1)>pq(n-1)>p; taking such a large aa gives b>0b>0 and realizes the ratio p/qp/q. Hence every rational number in [1,n−1)[1,n-1) occurs.