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 3 of 6: A weighted potential dominates t

Previous step Next step

q=\sum_{i=1}^n (i-1)a_i,\quad \Delta q\ge a\ge\gcd(a,b)=\Delta t\ \Rightarrow\ q-t\ \text{non-decreasing}

Detailed analysis

Write the $n$ numbers on the board in a row and let $q=\sum_{i=1}^n(i-1)a_i$ using their left-to-right positions, with $a+b$ always written in the position of the right-hand erased number. If positions $i<j$ held $a,b$ , the move changes $q$ by $(i-1)(1-a)+(j-1)((a+b)-b)=(i-1)+a(j-i)\ge a\ge\gcd(a,b)$ . Hence $q-t$ never decreases, so $q-t\ge q_0-t_0=\tfrac{n(n-1)}2$ throughout, where $q_0=\tfrac{n(n-1)}2$ is the initial value (all numbers equal to $1$ ) and $t_0=0$ .