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 1 of 6: Answer

\frac{t}{s}\in\mathbb{Q}\cap[1,n-1)

Detailed analysis

The possible values of $t/s$ are exactly the rational numbers in the interval $[1,n-1)$ .