MathDB

There are

1001

stacks of coins

S_1, S_2, \dots, S_{1001}

. Initially, stack

S_k

has

k

coins for each

k = 1,2,\dots,1001

. In an operation, one selects an ordered pair

(i,j)

of indices

i

and

j

satisfying

1 \le i < j \le 1001

subject to two conditions:
[*]The stacks

S_i

and

S_j

must each have at least

1

coin. [*]The ordered pair

(i,j)

must not have been selected before.
Then, if

S_i

and

S_j

have

a

coins and

b

coins respectively, one removes

\gcd(a,b)

coins from each stack. What is the maximum number of times this operation could be performed?
Galin Totev

1