There are 1001 stacks of coins S₁, S₂, ..., S₁₀₀₁. Initially, stack S_k has k coins for each k = 1,2, ...,1001. In an operation, one selects an ordered pair (i,j) of indices i and j satisfying 1 ≤ i < j ≤ 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?

(In reply to An upper bound and a possible solution by Steve Herman)

No hand-waving needed.  Any two consecutive numbers are relatively prime so just ensure there are always two consecutive.  Suppose 5 piles

Posted by Jer on 2025-05-17 22:51:06