12
$\begingroup$

Ten pirates are sitting around a table. Each of them has an even number of coins. At order of the captain, each pirate passes half of his coins to the neighbor to the right. After that round, each pirate with an odd number of coins gets 1 coin from the captain. The captain isn't sitting at the table and has an inexhaustible amount of coins. Then this procedure is repeated again until all pirates have the same amount of coins.

It that always possible?

$\endgroup$
  • 2
    $\begingroup$ Is the captain sitting at the table? Or does he "top-up" odd piles of coins with extra external coins? $\endgroup$ – Paul Evans Feb 21 at 17:46
  • $\begingroup$ The captain is not sitting at the table, he just has an (unlimited) pile of coins.. $\endgroup$ – ThomasL Feb 21 at 17:56
  • $\begingroup$ Edited that information into the question. If you're not happy with that please feel free to re-edit yourself but please include this added information. $\endgroup$ – Paul Evans Feb 21 at 18:23
7
$\begingroup$

Every round, each pirate:
- gains coins if the pirate to their left has more coins
- keeps the same number of coins if the pirate to their left has the same number of coins, or 2 fewer coins (in this case, the captain adds a coin)
- loses coins otherwise

The maximum number of coins held by any one pirate obviously cannot increase. Because of this, the captain cannot add coins forever.
The maximum number of coins also cannot decrease forever.

After the captain adds the last coin and the maximum stops decreasing, a pirate cannot have the maximum number of coins unless both they and the pirate to their left had the maximum number in the previous round.
The group of pirates with the most coins must eventually stop changing, since it cannot gain members and cannot become empty.

The only way that the group can never change is if each pirate to the left of a member is also a member.
This means that every pirate must be a member of the group, so all pirates have the most coins.

| improve this answer | |
$\endgroup$
2
$\begingroup$

The answer is:

All pirates will always end up with the same amount of coins.

Because:

In the first round there is one (or more) pirate(s) with the maximum amount of coins, called M. M can never be exceeded during all rounds, because the pirate next to him has the same amount or less coins. The sum of the coins (of all 10 pirates) will not decrease during a round, because all coins stay in the "game". Eventually coin(s) are added to the "game" by the captain. Therefore the sum of the coins will keep increasing. As mentioned before, M can't be exceeded. This holds that the captain keeps adding coins to the "game" untill all pirates have the same amount of coins. Note: this doesn't have to be M!

| improve this answer | |
$\endgroup$
-2
$\begingroup$

I'm guessing the answer is:

It always evens out.

Because:

I wrote this program:

from random import randint

for i in range(1000000):
    t = []
    for i in range(10):
        t.append(2*randint(10,1000))

    while not all(a==b for a, b in zip(t,t[1:])):
        n = [0]*10
        for i in range(10):
            n[i] = t[i-1]//2
            t[i-1] -= t[i-1]//2
        for i in range(10):
            t[i] += n[i]
            if t[i]%2==1:t[i]+=1

print("Finished")

And it always finishes.

| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ But how does that show it always finishes? How do you know that there isn't some counterexample above, say, 10 billion coins each? $\endgroup$ – Deusovi Feb 21 at 19:19
  • $\begingroup$ @Deusovi Quite right, I meant to submit that as a guess. Edited accordingly. $\endgroup$ – Paul Evans Feb 21 at 20:07
  • $\begingroup$ @Deusovi out of all examples you gave one that finishes before it starts ;) $\endgroup$ – Angkor Feb 26 at 21:57

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.