Pirates dividing booty around a circular table

Question

A group of pirates have plundered one of his majesty's cargo ships and they all carried as much gold coins as each one could find. When they get back to their ship, they sit at a round table and pass their gold around to the person to their left or right until each person has an equal number of gold coins.

Suppose there are $n$ pirates, $n$ seats at the table, each pirate can only pass coins to the pirate on his (no female pirates on this ship) left or right, the total number of coins $M$ is an integer multiple of $n$, the pirates are arbitrarily numbered, say clockwise, starting from some pirate seated in some fixed seat and $a_i$ is the number of coins belonging to pirate $i$. Furthermore, assume all pirates can see how many coins each pirate has, so they know $a_1,...,a_n$ as well as $M=\sum_{i=1}^n a_i$.

One way to accomplish this would be to have every pirate who has more than $\frac{M}{n}$ coins pass their excess to the right; continue doing this at most $n$ times until everyone has exactly $\frac{M}{n}$ coins.

For example, suppose there are $5$ pirates and
$a_1=15, a_2=a_3=0,a_4=50,a_5=0$
After round one, they would have:
$a_1=13, a_2=2,a_3=0,a_4=13,a_5=37$
After each of the next rounds, they would have:
$a_1=37, a_2=2,a_3=0,a_4=13,a_5=13$
$a_1=13, a_2=26,a_3=0,a_4=13,a_5=13$
$a_1=13, a_2=13,a_3=13,a_4=13,a_5=13$

However, one pirate decides that there might be a more efficient way. He counts that there were $2+37$ coins passed in the first round, $24$ passed in the second, $100$ passed in all. He found a way so that a much smaller number of coin passes could be done:

$a_1=13, a_2=2, a_3=24,a_4=13,a_5=13$
$a_1=13, a_2=13, a_3=13,a_4=13,a_5=13$

This way only requires $50$ coin passes. Note: pirate $1$ can pass to either pirate $2$ or pirate $n$, pirate $n$ can pass to $1$ or $n-1$, any other pirate $i\in (2,...,n-1)$ can pass to either $i-1$ or $i+1$.

The captain hears this and says "Avast ye. As much as I love coin passing I love other things like drinking and plundering even more. Me and me hearties have been passing these doubloons like a bunch of landlubbers. If ye could devise a strategy that would pass the least amount of doubloons, I would be much obliged."

How should they pass the coins to have the least number of coin passes given any valid starting number of coins and pirates?

---

The theme is related to the puzzle here. But, that requires all to pass half of their coins to the right only and requires the captain (not sitting at the table) to give 1 coin to each pirate with an odd number of coins after each round (so all pirates will always have an even number of coins).

Answer 1

Here is a recipe:

1. subtract the mean <a> from the pirate gold vector a
2. form the running sum A (A₁ = a₁, A₂ = a₁+a₂, A₃ = a₁+a₂+a₃ ..., A_n = 0 because of step 1)
3. subtract the median

Interpretation of result vector A:

If A_i is positive, pirate i passes A_i coins to pirate i+1, otherwise he receives -A_i coins from pirate i+1

Proof of correctness:

After subtracting the mean cell a_i contains pirate i's surplus or deficit if a_i is negative. Therefore pirate i should give away a_i coins in total. What he does give away is A_i - A_i-1 which does indeed equal a_i by construction. And what's more only a running sum over a can have this property which determines A up to constant offset.

Proof of optimality:

We need to shift A in such a way that sum |A|, the absolute sum over A, is minimized. It is well known (and easily verified) that subtracting the median does just that.

Example:

a = 15,0,0,50,0 -> 2,-13,-13,37,-13
A = 2,-11,-24,13,0 -> 2,-11,-24,13,0
So pirate 1 is to pay 2 to pirate 2 who also receives 11 from pirate 3 out of the 24 the latter receives from pirate 4 who also pays 13 to pirate 5.

Total number of coins x places shifted:

sum |A| = 2+11+24+13+0 = 50

Answer 2

An insight to get us started is that

Minimizing the number of coins transferred is equivalent to minimizing the sum of the distances that each coin travels, where distance is measured in terms of the number of times the coin is passed (which, in any optimal algorithm, will be the distance between where the coin started and where it ended). Thinking of it in terms of summing distances over individual coins instead of summing coin counts over individual transfers allows us to reason about optimality more easily.

With that in mind,

Consider all pirates with more than M/n coins. Select the one who is farthest away (in either direction) from any pirate with fewer than M/n coins (i.e. his minimum distance to a lacking pirate is maximized among all pirates with excess). The former pirate either sends enough coins to get the latter up to M/n, or enough coins for the former to get down to M/n (whichever is less), to the latter pirate (by way of one-hop transfers in the shorter direction). Once that is done, repeat from the beginning.

In case it isn't clear, this method provably works because at each step the number of pirates with exactly M/n coins is increased by either one or two (two in the case that the former pirate's excess is exactly the latter pirate's lack).

This should be optimal, since whatever coins the former pirate sends have to travel at least that far, and by doing this method they travel exactly that far. Note that if the former pirate somehow sends the coins less than that far, it has to be to an intervening pirate who used to have more than M/n coins and sent some of them, which is equivalent to the former pirate just sending his coins through the intervening pirate to wherever the intervening pirate's coins ended up (which again, is at least as far away as the latter pirate).