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 2 of 6: Bucket 1 counts moves; the ratio is at least 1

Previous step Next step

s=p-n,\quad p=\text{sum of the numbers on the board};\qquad t\ge s

Detailed analysis

Each move adds exactly one stone to bucket 1, so $s$ equals the number of moves made, and if $p$ denotes the sum of the $n$ numbers on the board then each move increases $p$ by exactly $1$ (it removes $a+b$ and writes back $1+(a+b)$ ), so $p=n+s$ . Since $\gcd(a,b)\ge1$ on every move, bucket 2 gains at least as many stones as bucket 1 on each move, so $t\ge s$ , i.e. $t/s\ge1$ .