Category: probability

538’s Pirate Logician Puzzle

538 had a fun riddler this past week:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

  • Self-preservation: A pirate values his life above all else.
  • Greed: A pirate seeks as much gold as possible.
  • Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is my answer:

The Captain will propose the following distribution, which will be accepted by all pirates who are offered a coin: 6 gp for himself, and 1 gp each for pirates 2, 4, 6, and 8 (where lower numbers indicate lower ranks).

To see why, we can work backwards from the end game. If it comes down to just P2 and P1, P2 will propose taking all the gold for himself; since 50% is sufficient to ratify a plan, it will be go into effect even though P1 will vote against it. So what does P3 have to offer to do to get a proposal approved? He clearly can’t get the support of P2. (Even if he offered P2 all the gold, P2 would still vote against the plan on account of bloodthirst!) But 1 gp is sufficient to get a vote from P1. P3 doesn’t need to offer P2 anything, so he can take the balance (9 gp) for himself. Continuing this backwards reasoning, P4 also needs 1 vote other than his own . It is most easily acquired from P2, who will end up with nothing if things proceed to the next stage. So P4 can offer P2 1 gp, keep 9 gp for himself, and offer nothing to P1 or P3. The ideal solution for each pirate is thus as follows:
s(P2) = {0, 10} (meaning 0 gp for P1 and 10 gp for P2)
s(P3) = {1, 0, 9}
s(P4) = {0, 1, 0, 9}
s(P5) = {1, 0, 1, 0, 8}
s(P6) = {0, 1, 0, 1, 0, 8}
s(P7) = {1, 0, 1, 0, 1, 0, 7}
s(P8) = {0, 1, 0, 1, 0, 1, 0, 7}
s(P9) = {1, 0, 1, 0, 1, 0, 1, 0, 6}
s(P10)={0, 1, 0, 1, 0, 1, 0, 1, 0, 6}
In each case, every pirate who is offered a gold piece will vote for the proposal, since the alternative is to end up with nothing. Every pirate who is offered nothing will, of course, vote against the proposal.

What about the extra credit problem, with g gold pieces and P pirates. The same basic reasoning applies:

S(P2) = {0, g}
S(P3) = {1, 0, g-1}
S(P4) = {0, 1, 0, g-1}
S(P5) = {1, 0, 1, 0, g-2}
S(P6) = {0, 1, 0, 1, 0, g-2}

For any even P, the captain will award 1 gp to each even-numbered pirate other than himself, and take all the remaining gold pieces for himself.
For any odd P, the captain will award 1 gp to each odd-numbered pirate other than himself, and take all the remaining gold pieces for himself.

But what if there are not enough gold pieces? E.g. consider 2 gp for 5 or 6 pirates? In this case, the captain will be forced to distribute all of the gold to others just to save his own hide: the rule above still holds but leaves the captain with nothing. 2 gp for 7 pirates is even worse: there is no proposal the captain can make that will get 3 (or more) votes other than his own. There are just too many bloodthirsty pirates with nothing to lose. Whatever P7 proposes, it will be rejected and he will be killed. What about 2 gp for 8 pirates? Now, a new wrinkle is introduced: P7 will vote for P8’s proposal to save his own life, even if P8 offers him no gold. Furthermore, pirates will decide whether to vote for P8’s proposal not by comparing their outcome to P7’s doomed hypothetical proposal, but rather to P6’s proposal. Therefore, P8 needs to offer gold pieces to 2 of P1, P3, and P5. Those 2 votes, plus the votes of P8 and P8, will be enough to ratify.

What about P9? P9 can count on P7’s vote and his own vote. He needs 3 more votes, but with only 2 gps to spread around, he isn’t going to get them.

And P10? He can count on P7 and P9’s vote (even if he offers them nothing), and his own. So he only needs 2 more votes. Pirates will decide by comparing his proposal to P8’s hypothetical proposal. But P8 could propose any of three possible distribution schemes, which complicates the votes of P1, P3, and P5. Each has only a 2/3 probability of getting any gold if P10’s proposal fails (or an expected value of 2/3 of a gp), so if they are offered a gp by P10, they will support the proposal. So P10’s proposal will pass.

11 pirates and 2 gp? P11 can count on the votes of himself, P7, and P9. He needs 3 more votes, and has no way to secure them with only 2 gp. Any proposal he makes will fail.

12 pirates and 2 gp? P12 can count on the votes of himself, P7, P9, and P11. He needs 2 more votes. By offering 1 gp each to 2 of P2, P4, P5, and P6 (each of whom otherwise has only a 50% chance of receiving a gp), he can secure them.

With 2 gp, this odd-even pattern will repeat indefinitely. I’m not sure of the general rule, but things get tricky when there are a lot more pirates than gold pieces.

A Histogram of the Monster Data

And here is a histogram representing the distribution of the number of monsters that had to be killed in order to acquire all three types of gems, produced with the following code:

import matplotlib.pyplot as plt
%matplotlib inline
plt.hist(monsterCount,bins=maxMonsterCount-1)

Monster-histogram

Note that this is for a different run of the code than the sample output I showed in the previous post. In this particular 100,000 trial run, there was one trial where it was necessary to kill 67 monsters in order to acquire all three gem types!

Also, copying the image produced a .png file with partial transparency, which has resulted in black-on-gray numbers here that aren’t very legible. Sorry about that. I think there are mechanisms for displaying Python output graphs in a browser window without just copying and pasting images, but I haven’t figured them out yet.

538’s Monsters and Gems Puzzle

538 has a weekly riddler post, and I thought I would try this week’s riddle:

A video game requires you to slay monsters to collect gems. Every time you slay a monster, it drops one of three types of gems: a common gem, an uncommon gem or a rare gem. The probabilities of these gems being dropped are in the ratio of 3:2:1 — three common gems for every two uncommon gems for every one rare gem, on average. If you slay monsters until you have at least one of each of the three types of gems, how many of the most common gems will you end up with, on average?

Here is the answer I submitted:

I couldn’t figure out how to reason about this with the probability theory that I know, so I thought I would try to simulate it. I’ve been playing around with Python recently, so I wrote a program that simulates an arbitrary number of trials. Running this repeatedly with 100,000 trials, rounded averages were mostly consistent to 2 decimal places, although sometimes the last decimal place varied by one: 3.65 common gems, 2.43 uncommon gems, 1.22 rare gems, 7.30 monsters killed.

On average it should take 6 dead monsters to get a rare gem. By then, most of the time we would expect that both common and uncommon gems would have appeared. So it’s surprising to me that the average is as much higher than 6 as it is. Intuitively, I think part of what is going on is that because it always takes at least 3 dead monsters to get all 3 gem types, the cases where a rare gem is drawn early on aren’t able to “balance out” the cases where it takes a really long time, as would be the case in a simpler probability distribution. About 15% of the time, it takes 12 or more kills to get all three gem types. I’m no closer, though, to a mathematical derivation of the exact answer.

I have pasted below a sample output from the program, and below that the program itself.

number of trials: 100000
Average number of common gems: 3.64636
Average number of uncommon gems: 2.43568
Average number of rare gems: 1.21557
Average number of monsters killed: 7.29761
max monster count 56
1 dead monsters: 0 (0.000% | 0.000%)
2 dead monsters: 0 (0.000% | 0.000%)
3 dead monsters: 16744 (16.744% | 16.744%)
4 dead monsters: 16700 (16.700% | 33.444%)
5 dead monsters: 13746 (13.746% | 47.190%)
6 dead monsters: 10839 (10.839% | 58.029%)
7 dead monsters: 8446 (8.446% | 66.475%)
8 dead monsters: 6552 (6.552% | 73.027%)
9 dead monsters: 5176 (5.176% | 78.203%)
10 dead monsters: 3937 (3.937% | 82.140%)
11 dead monsters: 3241 (3.241% | 85.381%)
12 dead monsters: 2689 (2.689% | 88.070%)
13 dead monsters: 2104 (2.104% | 90.174%)
14 dead monsters: 1653 (1.653% | 91.827%)
15 dead monsters: 1376 (1.376% | 93.203%)
16 dead monsters: 1200 (1.200% | 94.403%)
17 dead monsters: 907 (0.907% | 95.310%)
18 dead monsters: 807 (0.807% | 96.117%)
19 dead monsters: 620 (0.620% | 96.737%)
20 dead monsters: 529 (0.529% | 97.266%)
21 dead monsters: 443 (0.443% | 97.709%)
22 dead monsters: 382 (0.382% | 98.091%)
23 dead monsters: 312 (0.312% | 98.403%)
24 dead monsters: 305 (0.305% | 98.708%)
25 dead monsters: 221 (0.221% | 98.929%)
26 dead monsters: 178 (0.178% | 99.107%)
27 dead monsters: 139 (0.139% | 99.246%)
28 dead monsters: 129 (0.129% | 99.375%)
29 dead monsters: 95 (0.095% | 99.470%)
30 dead monsters: 99 (0.099% | 99.569%)
31 dead monsters: 60 (0.060% | 99.629%)
32 dead monsters: 58 (0.058% | 99.687%)
33 dead monsters: 46 (0.046% | 99.733%)
34 dead monsters: 50 (0.050% | 99.783%)
35 dead monsters: 33 (0.033% | 99.816%)
36 dead monsters: 31 (0.031% | 99.847%)
37 dead monsters: 25 (0.025% | 99.872%)
38 dead monsters: 25 (0.025% | 99.897%)
39 dead monsters: 19 (0.019% | 99.916%)
40 dead monsters: 19 (0.019% | 99.935%)
41 dead monsters: 14 (0.014% | 99.949%)
42 dead monsters: 15 (0.015% | 99.964%)
43 dead monsters: 6 (0.006% | 99.970%)
44 dead monsters: 5 (0.005% | 99.975%)
45 dead monsters: 6 (0.006% | 99.981%)
46 dead monsters: 4 (0.004% | 99.985%)
47 dead monsters: 4 (0.004% | 99.989%)
48 dead monsters: 1 (0.001% | 99.990%)
49 dead monsters: 2 (0.002% | 99.992%)
50 dead monsters: 0 (0.000% | 99.992%)
51 dead monsters: 3 (0.003% | 99.995%)
52 dead monsters: 3 (0.003% | 99.998%)
53 dead monsters: 1 (0.001% | 99.999%)
54 dead monsters: 0 (0.000% | 99.999%)
55 dead monsters: 0 (0.000% | 99.999%)
56 dead monsters: 1 (0.001% | 100.000%)

Here is my python 3 code:

import random
commonCount=[]
uncommonCount=[]
rareCount=[]
monsterCount=[]
numTrials = 100000

maxMonsterCount = 0;

for i in range (0,numTrials):
    commonCount.append(0)
    uncommonCount.append(0)
    rareCount.append(0)
    monsterCount.append(0)

for i in range (0,numTrials):
    while (commonCount[i]==0 or uncommonCount[i]==0 or rareCount[i]==0):
        monsterCount[i] +=1
        if (monsterCount[i] > maxMonsterCount):
            maxMonsterCount = monsterCount[i]
        monster = random.randrange(1,7)
 #randrange syntax includes the first parameter, but excludes the second       
        if (monster==1 or monster==2 or monster==3):
            commonCount[i] += 1
        elif (monster==4 or monster==5):
            uncommonCount[i] += 1
        elif (monster==6):
            rareCount[i] += 1
        else:
            print("ERROR!")            
# Don't run the following lines unless numTrials is small ...
#    print ("i =",i)
#    print ("common:", commonCount[i])
#    print ("uncommon:", uncommonCount[i])
#    print ("rare:", rareCount[i])
#    print ("total:", monsterCount[i])

commonTotal = 0;
uncommonTotal = 0;
rareTotal = 0;
overallTotal = 0;

for i in range (0, numTrials):
    commonTotal += commonCount[i]
    uncommonTotal += uncommonCount[i]
    rareTotal += rareCount[i]
    overallTotal += monsterCount[i]

commonAverage = commonTotal/numTrials
uncommonAverage = uncommonTotal/numTrials
rareAverage = rareTotal/numTrials
totalAverage = overallTotal/numTrials
print ("number of trials:",numTrials)
print ("Average number of common gems:",commonAverage)
print ("Average number of uncommon gems:",uncommonAverage)
print ("Average number of rare gems:",rareAverage)
print ("Average number of monsters killed:", totalAverage)

print("max monster count", maxMonsterCount);

killDistribution=[]
for a in range (0,maxMonsterCount+2):
    killDistribution.append(0)
for i in range (0,numTrials):
    killDistribution[monsterCount[i]] += 1

cumulativePercentage = 0;
for a in range (1,maxMonsterCount+1):
#1 and 2 should always be zero, but I like to leave them in anyway.
    cumulativePercentage += killDistribution[a]/numTrials*100
    print ('{: d} dead monsters: {: d} ({:04.3f}% | {:04.3f}%)'.format(a,killDistribution[a],killDistribution[a]/numTrials*100,cumulativePercentage))