perplexus.info :: Just Math : Coin Stack Manipulation

Coin Stack Manipulation (Posted on 2025-05-17)

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?

No Solution Yet Submitted by Danish Ahmed Khan

Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

An upper bound and a possible solution

| Comment 1 of 2

Interesting problem. I believe the answer is 250,500.

Let's solve a different problem, where instead of removing the GCD from each pile in the pair, you only remove 1 coin.

Let's start by pairing pile 1001 with each of the other 1000 piles, so 1000 operations. We remove one coin from each pile.

We have now exhausted pile 1, and pile 1001 can no longer be paired, so we are left with 999 piles having quantity 1, 2, ... and 999.

Now pair pile 1000 (whose qty is now 999) with the other 998 piles, so 998 operations.

Perform this process for a total of 499 times, at which point piles 1-499 are empty, pile 500 has qty 1, pile 501 has qty 2, pile 502 has quantity 3, and piles 503-1001 can no longer be paired.

There have been 1000 + 998 + ... + 2 = 250,500 operations. In general, for 2k+1 piles, there will have been k*(k+1) operations. This is clearly an upper limit for the problem answer,

Now, for some hand-waving.

The same 250,500 pile pairings could have been done in any order. I might be wrong, but I assert without proof that the order of pairings can be arranged so that the number of stones in the two paired piles are always relatively prime before the pairing. In which case, the puzzle answer is also 250,500.

Can anybody prove me wrong?

Edited on May 17, 2025, 4:02 pm

Posted by Steve Herman on 2025-05-17 16:01:10

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info