puzzles – George Schneiderman

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.

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

Category: puzzles

538’s Monsters and Gems Puzzle