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 4 of 6: Upper bound for q from a_i>=1

Previous step Next step

q\le (n-1)p-\tfrac{n(n-1)}2 = (n-1)s+\tfrac{n(n-1)}2

Detailed analysis

Since each $a_i\ge1$ , for each $i$ we have $(i-1)a_i\le(n-1)a_i-(n-i)$ , and summing over $i$ gives $q\le(n-1)p-\sum_{i=1}^n(n-i)=(n-1)p-\tfrac{n(n-1)}2=(n-1)s+\tfrac{n(n-1)}2$ using $p=n+s$ .