6
$\begingroup$

There are 40 pirates, designated as P1, P2, ...... P40, respectively. They aim to divide 1,987 gold coins using a two-stage division scheme:

  • In the first stage, P1 initially splits all the coins into two piles. Then, P2 splits one of the piles into two piles, followed by P3 splitting one of the remaining piles into two, and so on, until P40 completes the 40th split, resulting in 41 piles of gold coins.

  • In the second step, P1 takes the largest pile of gold coins, followed by P2 taking the largest pile from the remaining piles, and so on, until all pirates have taken their share except for the 41st pile, which is left stored and sealed.

Each pile must contain at least one gold coin and the gold coins cannot be broken.

What is the maximum amount of gold coins that P1 can ensure he gets?

$\endgroup$
5
  • 1
    $\begingroup$ is this rehprased by ChatGPT? :) it is so robotic sentence. $\endgroup$
    – Oray
    Commented Apr 7, 2023 at 13:19
  • 1
    $\begingroup$ @Oray Yes, English is not my native language, and it has happened before that my own written text produced ambiguity and caused trouble for solvers, so I hope ChatGPT optimizes the expression. $\endgroup$
    – Pumbaa
    Commented Apr 7, 2023 at 13:24
  • 1
    $\begingroup$ you should say Chatgpt to make sentence in a verbal way, this is so formal writing :D $\endgroup$
    – Oray
    Commented Apr 7, 2023 at 13:26
  • $\begingroup$ This shows the difficulty of making a multiperson game where the behavior is well defined. What one pirate gets depends on what the others do, and what they do doesn't change what they get. $\endgroup$ Commented Apr 8, 2023 at 3:33
  • $\begingroup$ Can you clarify what the goals of the other pirates are? Is it to minimize the amount of coins P1 gets, to maximize their own coins, or something else? $\endgroup$
    – isaacg
    Commented Apr 8, 2023 at 14:21

4 Answers 4

5
$\begingroup$

If there is an alliance formation (there can be several such cases), then in the worst case the rest of the pirates form an alliance and go against $P_1$. In this case, $P_1$ can ensure:

$\left\lceil\frac{1986}{40}\right\rceil = 50$ Gold Coins (by dividing initial pile into $1986$ and $1$ piles)

Thus, after $40$ divisions, we would have:

Twenty-six piles of $50$ coins, fourteen piles of $49$ coins, one pile of only $1$ coin.


However, if we assume NO any alliance formation (which also ensures no fruitful communication among pirates), and that every pirate always tries to maximize individual wealth whatever the current situation is, then $P_1$ can ensure:

$62$ Gold Coins

This is because:

There is an invariant hidden in the individual strategies.

Interesting claim (Invariant):

Each pirate will try to maximize the second shortest pile that remains after their division.

This is because:

After $i$ divisions, the current second shortest pile is the current $i^{th}$ tallest pile. The $i^{th}$ maximum can increase later on only when some following pirate is biased towards $P_{i}$, but in the worst case that pirate can always keep the $\delta$ aligned with some other pile and it won't affect their own share. So $P_i$ must greedily maximize the size of the $i^{th}$-tallest pile to ensure that the current $i^{th}$ maximum is as high as possible.

Notice that if we think backwards, this is very trivial for the last pirate $P_{40}$ as the second minimum overall will be $P_{40}$'s share. Similarly, $P_{39}$ will try to maximize the $39^{th}$ tallest pile...and so on.

Finding the answer to above strategy is simple. This is because:

$P1$ divides the initial pile into $1986$ and $1$ as it maximizes the second minimum. For the rest of the pirates, dividing the tallest pile into two halves always maximizes (or does not affect) the second minimum. Sometimes it would also be possible to divide in a different manner, but dividing the maximum into halves is the worst case for the rest of the pirates.

So now, the divisions occur as follows:

$P_1$ creates piles of sizes $\{1986, 1\}$

$P_2$ creates piles of sizes $\{983, 983, 1\}$... and so on.

The maximum after $2^{i}$ divisions is:

$\left\lceil\frac{1986}{2^{i}}\right\rceil$

So after $32$ divisions, we would have:

Two piles each of $63$ coins, thirty piles of $62$ coins, one pile of only $1$ coin.

Thus, after $40$ divisions, we would have:

Twenty-four piles of $62$ coins, two piles of $32$ coins, fourteen piles of $31$ coins, one pile of only $1$ coin.

Note that this gives the maximum possible value $P_{1}$ can ensure, given that all are trying to maximize their individual score. That is $P_{i}$ won't bother about how the earlier pirates have performed their division, but rather focus on maximizing her guaranteed wealth from the current coin-set she has. Everyone is aware that there is no alliance formation anywhere, and that all other pirates are intelligent enough.

$\endgroup$
2
  • 1
    $\begingroup$ I'm not convinced of that "always halving the largest pile" thing. Consider the case of three pirates, 61 coins. If the first splits 60-1 the second should not split 30-30-1 because the best thing for the last would then be 30-15-15-1 whereas after 40-20-1 the best thing for the last would be 20-20-20-1. $\endgroup$
    – loopy walt
    Commented Apr 9, 2023 at 7:16
  • $\begingroup$ @loopywalt Yes you're right. I've analyzed this twice, $P_{i}$ should not greedily maximize the $i^{th}$ largest pile (I'm running in a loop with this question, before writing this answer I thought of this, then I don't remember why I changed it, again I'm changing back). However, there's another way to somehow force the moves of the next pirate. I will add it to the above answer soon. $\endgroup$
    – thisIs4d
    Commented Apr 9, 2023 at 11:45
4
$\begingroup$

The first pirate would love to end up with one pile of 1947 coins and 40 piles of 1 coin. That would be the best for that pirate. So the first pirate definitely splits into and 1986 and 1.

The last pirate would like 40 piles of either 49 or 50, so that they will not be frozen out. Everyone else would like more piles of 1, since this makes the piles they are choosing from more likely to have more than 50 coins.

The first pirate, to ensure the most coins possible, needs to explain this to each choosing pirate in turn. "Listen, P2, I know you want to split that big 'un so we can both get half, but the pirates after you will just keep splitting it. You're best served by just pulling off 1. If anyone after you splits what's left, you'll be right in line after me for the second biggest."

Assuming this line of logic holds up, eventually we will be at P21 and there will be 20 single coins on the table. P21 will not want to pull off a single coin - the 19 pirates picking piles after P21 are getting singles, but P21 is going to get the smallest thing left after dividing up the 1967 coins still in the big pile. It's in P21's interest to split this pile into 984 and 985. P22 (who is getting 1 coin no matter what) will at best split the first into 492 and 492, and P23 the other into 492 and 493. P23,24,25, and 26 give us 7 246s and a 247. Then up to 34 gets 15 123s and a 124. 6 of these get split; let's say the 124 does, for 2 62's and 5 61/62 pairs, leaving 10 123s.

If the pirates in the latter half are surly and grumpy, knowing they will only get one coin, they may split their piles less evenly, creating single-coin or [otherwise less than 50] piles. This will increase what P1 gets. P1 can't be sure they will do this, though certainly encouraging P2 through P20 to guarantee single-coins for 22 through 40 is likely to make them feel like upsetting others. All P1 can ensure is one of those 123-coin piles (or better) once 1967 coins are still in a single pile on P21's turn.

$\endgroup$
3
$\begingroup$

As this question does not require the remaining pirates to each ensure their own maximum, the answer is trivial.

$$\left\lceil\frac{1986}{40}\right\rceil = 50$$ After the first pirate splits the coins into piles of 1986 coins and 1 coin, the next 26 pirates can each split 50 coins from the largest pile. Then the remaining pirates can each split 49 coins from the largest pile. The result will be 26 piles of 50 coins, 14 piles of 49 coins, and one single coin left unclaimed.

I don't think this is intended, as the second pirate can (and will) ensure a greater number of coins for himself, which necessarily provides a greater number of coins for the first pirate.

$\endgroup$
3
$\begingroup$

The first pirate can only guarantee 50 coins.

edit: improved motivation.

P40 Has the last action, thus a lot of influence over P39.
1/ It will tell P39 that they will get the same amount, unless the largest stack is odd and splitting that in half gives P40 more.
2/ It will also say that it will do exactly what P39 wants, as long as this does not violate 1/
Now P39 has the same power relative to P38 and it is best to maximize P40s (and their own) winnings by telling P38 the same, then P38 will tell this to 37 etc.

small examples:

small example 1: 4 pirates 9 coins P1 splits of 1
P2 splits of 1? P4 will get 1 P4 will makes sure P3 gets one, P3 follow its rule 1 by splitting of 1 -> division 5111
P2 splits of 2? P4 will get 1 if they split of 1 or 3, since P4 cannot get 2 and thus splits the group of 2, so P4 will split of 2 -> division 2222 (best option for P2)
P2 splits of 3? P4 will get 1 P4 will makes sure P3 gets one, P3 follow its rule 1 by splitting of 1 from the group of 3 -> division 5111
P2 splits of 4? P4 will get 1 if they split of 1, since P4 cannot get 2 and thus also splits of 1, so P4 will split of 2 -> division 2222 (same best outcome for P2)

small example 2: 4 pirates 10 coins
P1 splits of 1
P2 splits of 1? P4 will get 1. P4 will makes sure P3 gets one, P3 follow its rule 1 by splitting of 1 -> division 6111
P2 splits of 2? P4 will get 1 if P3 split of 1 or 3, since P4 cannot get 2 and thus splits the group of 2, so P4 will split of 2 -> division 3222
P2 splits of 3? P4 will get 1. P3 can also split of 3 and p4 has only 1 option -> division 3321 (best option for P2)
P2 splits of 4? P4 will get 1 if P3 split of 1, and then P3 will get 1. >! Thus P3 will split up 2 and p4 will split of 2 from the other group -> division 3222

However P1 seems to have a 'better' strategy if there are more coins.
small example 3: 4 pirates 41 coins
P1 splits 11-30
P2 splits 11-11-19
P3 splits 11-11-10-9 end 11-10-9-9-2
However, P2 will minimize P1 winnings as threatened and instead get 10 e.g. like this:
P1 splits 11-30
P2 splits 10-1-30
P3 splits 10-1-10-20 end 10-10-10-10-1
So P1 will not get more than 10. (but can take 4 to get to 10-9-9-9-4)

expected outcome:

P1 splits 1912-75
P2 splits 1912-25-50
Considering the threats, it is in the best interest of all others to split of 49 (or a multiple), for an end result of:
50-50-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 -
49-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 -15

Note however small example 2. One cannot get more, but one can give more to the earlier in line, thus more dangerous pirate.

final answer:

P1 splits 1960-27 (looking dangerously at P39)
P2 - P38 split of 49
P39, afraid of P1 will split of 50 leaving 97 to split by P40 and still gets 49
50-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 -
49-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-49 - 49-49-49-49-48 -17
Being pirates, all laugh at P40

original motivation

The first pirate will suggest the first 20 pirates can group together and separate 1 coin. Then the last 19 will get only one coin and P1 gets at least 1987/21 = 95.

Of course, as soon as the first pirate has done the speech and separated a coin, the last 20 should tell P2 that P2 will get 1 coin unless he cooperates with their plan, which they can enforce if the others follow P1s plan. Obviously, their plan is to divide the coins evenly, and P2 sets aside 50 coins.

Similarly, for all n it is in Pn's interest to separate 50 or 49 coins (that Pn-1 will get). Eventually it is P40's turn, who will split the remaining 98 coins of the 'big stack' in 2. -- This works since any pirate left out of their fair share can take revenge on the previous pirate by putting 1 coin apart. (Assuming anyone dares to bring forward this plan that P1 will not like.)

$\endgroup$
2
  • $\begingroup$ Why does the third paragraph work? If only 20 people go to P2 they can't say P2 will only get 1. $\endgroup$ Commented Apr 8, 2023 at 3:34
  • $\begingroup$ It works "if the others follow the original plan" and thus there are enough stacks of 1, that assumption is a bit shortsighted ; therefor my edit/improved motivation. $\endgroup$
    – Retudin
    Commented Apr 8, 2023 at 12:07

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