Had to take a break from last week’s Riddler, Can You Solve The Puzzle of the Overflowing Martini Glass, partly because I was short on time, but mostly because I had a lot of trouble figuring it out. My 17 year old brother and his friends were able to figure it out, which was embarrassing reminder of how much Calc I’d forgotten.
This weeks FiveThirtyEight Riddler, Can You Slay The Puzzle of the Monsters Gems was:
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?
Same with all the other Riddlers, first thing I like to do is simulate the problem, since it’s generally gives you a good starting point to the problem, and provides a way to check the solution.
The above’s just a quick gif of the simulation output. I only went up to n = 50, since the average gems doesn’t change much after n = 50. I found that the amount of common, uncommon and rare gems we see when we have all the gems are roughly 3.6, 2.4 and 1.2 gems respectively after a large amount of iterations (n =1000). That makes sense since that falls into the 3:2:1 probability we’re given in the problem.
This problem is actually really similar to the famous Coupon Collector problem. It’s a little different in that we deal with unequal probabilities. This can be dealt with the Maximum-Minimums Identity, (formula below) which is outlined in Section 3.1 of The Coupon Collectors Problem by Marco Ferrante and Monica Saltalamacchia.
We’ll start with the following variables:
Emonsters = Expected # of Slayed Monsters to Collect All Gems
Pcommon = Probability of Getting a Common Gem = 1/2
Puncommon = Probability of Getting an Uncommon Gem = 1/3
Prare = Probability of Getting a Rare Gem = 1/6
The maximum-minimums equation, for the sake of our problem, is essentially:
Emonsters = [ Emonsters for Common gem + Emonsters for Uncommon gem + Emonsters for Rare gem ] –
[ Emonsters for Common or Uncommon Gem + Emonsters for Common or Rare gem + Emonsters for Uncommon or Rare gem ] +
[ Emonsters for Common, Uncommon, or Rare Gem ]
Expected monsters for each gem is just the reciprocol of the probablity (Emonsters for Uncommon gem = 1/Pcommon). The probability for Emonsters for Common or Uncommon Gem is also easily calculated.
Pcommon, uncommon = Pcommon, + Puncommon = 1/2 + 1/3 = 5/6
So our Emonsters equation is:
Emonsters = [ 1/PCommon + 1/PUncommon + 1/PRare] –
[ 1/PCommon, Uncommon + 1/PCommon,Rare + 1/PUncommon,Rare] +
[ 1/PCommon, Uncommon,Rare]
Plug in our values and we get:
Emonsters = [2+3+6] – [6/5 + 3/2 + 2] + 1 = 11 – 4.7 + 1 = 7.3 Monsters to Slay to get all Gems
The question asks for expected number of common gems when you’ve gotten at least one every gem. That’s simply
Emonsters * PCommon = 7.3 * 1/2 = 3.65
An expected value of 3.65 Common Gems is consistent with the values we got from our simulated experiment.