Problem 5

Let

n\ge3

be a fixed integer. The number

1

is written

n

times on a blackboard. Below the blackboard, there are two buckets that are initially empty. A move consists of erasing two of the numbers

a

and

b

, replacing them with the numbers

1

and

a+b

, then adding one stone to the first bucket and

\gcd(a,b)

stones to the second bucket. After some finite number of moves, there are

s

stones in the first bucket and

t

stones in the second bucket, where

s

and

t

are positive integers. Find all possible values of the ratio

\dfrac{t}{s}

Step 5 of 6: Combine to get the strict upper bound

Previous step Next step

t< (n-1)s \implies \tfrac{t}{s}<n-1

Detailed analysis

By symmetry we may arrange the first move to use the two rightmost initial $1$ 's. Immediately afterward, $s=t=1$ and $q=q_0+(n-1)=\tfrac{(n+2)(n-1)}2$ . Since $q-t$ never decreases, every later state satisfies $q\ge t+\tfrac{(n+2)(n-1)}2-1$ . Combining this with $q\le(n-1)s+\tfrac{n(n-1)}2$ gives $t\le(n-1)s-(n-2)<(n-1)s$ because $n\ge3$ . Together with $t\ge s$ , this proves $t/s\in[1,n-1)\cap\mathbb Q$ .