3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ FYI: I added proof to my answer. $\endgroup$ – Albert.Lang Mar 7 at 22:02
4
$\begingroup$

Here is a recipe:

1. subtract the mean <a> from the pirate gold vector a
2. form the running sum A (A1 = a1, A2 = a1+a2, A3 = a1+a2+a3 ..., An = 0 because of step 1)
3. subtract the median

Interpretation of result vector A:

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

Proof of correctness:

After subtracting the mean cell ai contains pirate i's surplus or deficit if ai is negative. Therefore pirate i should give away ai coins in total. What he does give away is Ai - Ai-1 which does indeed equal ai 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

$\endgroup$
3
  • $\begingroup$ This answer would really profit from proper typography. Now all the variable names look like the English words "I, a and ai", start-of-sentence capitalisation completely changes their meaning, and when the verb is accidentally missing from the sentence (like in the second spoiler block), there would still be a slim chance of correctly parsing the sentence without severely spraining the brain muscle. :-) $\endgroup$ – Bass Mar 21 at 14:51
  • $\begingroup$ @Bass Ai's a word? Anyway, I've added some formatting. $\endgroup$ – Albert.Lang Mar 21 at 15:17
  • $\begingroup$ Well, not all that common (when not capitalised), but yeah, it is. Thanks for the edit! $\endgroup$ – Bass Mar 21 at 15:21
2
$\begingroup$

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).

$\endgroup$
2
  • 2
    $\begingroup$ Isn't something like 4,4,4,4,3,7,4,4,2,4,6,4,4,1,5,4,4,4,4 a counter example? The most remote above average guy would be 6 and the nearest sub average to him would be 2. But transferring between those two is clearly not optimal (because 7->2 6->1 is better than 6->2 7->1). $\endgroup$ – Albert.Lang Mar 6 at 18:51
  • 1
    $\begingroup$ Ah, good point! The circular nature is what makes this tough. Without that aspect (i.e. if the underlying distances are a metric), you can make an argument like this by just enforcing that you always go from left to right, and anytime you find a pirate with too many or too few coins, you correct his pile by giving to/taking from the nearest pirate to his right with the opposite problem. I'll leave my answer as a starting point. $\endgroup$ – hdsdv Mar 6 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.