How many M&Ms do you have to draw from an infinite box to ensure you have 1 of each color?

Question

I recently ran across this interview screening question:

You have a bag that contains 10 different colors of M&Ms. There is an equal amount of each color of M&M. You do not know how many M&Ms start in the bag or are left in the bag at any given point. How many M&Ms do you have to draw to ensure that you have 1 of each of the 10 colors?

My initial thought was that it must be related to how many are left in the bag, but the interviewer was clear that you do not know how many are left in the bag.

My next thought was that you must empty the bag, since, for any number you pull, you don't know that the bag doesn't contain many times more still remaining.

For example, 55 would suffice as to ensure all 10 colors if only 60 M&Ms existed in the bag, but 55 would not suffice if there were 500, and you do not know whether there are 50, 500, or potentially many more.

Thus, it seems to me that any other answer must be a multiple or variable related to either the total number or the number remaining in the bag. However, you know neither the total number or the number remaining.

The answer I ended up giving was the only one that didn't seem to get shot down: you must empty the bag. However, the interviewer said this is incorrect, and my intuition is that there is a better answer as well, but I'm having trouble finding it.

How do you solve this problem?

Answer 1

My thoughts:

If there is an infinite number of M&M's then there is no solution; you can never guarantee you'd pull at least one of each colour.

For a finite number, the amount you have to take out can only be expressed with respect to the total number in the bag, and will constantly change as you have more information.

For example, once you pull the first M&M, we deduce that, at this point, you would have to claim that you need to take them all out (since there could just be 1 of each). If you pull a duplicate M&M, then the most you would need to withdraw is all but 1. Formally, at each M&M pull $p_i$ at time $i$ from a bag with $N$ M&M's in, you can claim that you would need to pull at most $N-(x-1)$ M&M's from the bag, where $x$ is the number of M&M's you have of the model colour.

Answer 2

If the bag is infinite, as in the title, you cannot guarantee that you draw all the colors with any finite number of draws. For a large number $n$ of draws the chance that you are missing a color is about $10\cdot 0.9^n$, which becomes very small when $n$ is large but remains greater than $0$.

If the bag contains $N$ candies, you must draw $0.9N+1$ to guarantee you get at least one of each color, because the first $0.9N$ could be all the ones of nine different colors. If you don't know $N$ you can't compute the number, so I think you were expected to express it as the formula.

Answer 3

Answer number 1: (No one says my stopping condition must be unconditionally set before starting.) You successively draw M&Ms until you have $10$ different colors. Since the bag may contain arbitrarily many M&Ms, there is no a priori upper bound on the number of M&Ms drawn. A hard lower bound is that you must draw at least 10 M&Ms.

Answer number 2: (No one says my stopping condition cannot be dependent on a parameter I do not know.) You guarantee you have at least one M&M of each color if you draw 90% + 1 M&Ms. The 90% are guaranteed to exhaust nine of the ten colors and the "+1" guarantees at least one instance of the tenth color.

Answer number 3: What M&Ms? Someone seems to have eaten all the M&Ms. (wipes chocolate from corner of mouth)

---

Added in edit:

First, there have only been eight colors (blue, brown, green, orange, red, tan, violet, and yellow) of M&Ms and only ever six in one bag. So I don't know what's in this bag, but it's not M&Ms. Second, while one can get bags of single colors that are not in that list, for instance "electric green", all such bags are monochromatic. Finally, the largest bag of either kind sold is 10 pounds (about 4.5 kg). (Look, M&Ms and I have a long history...) Given the above, even emptying the bag won't produce ten colors...

Answer 4: Consequently, the bag of M&Ms is entirely imaginary, so any answer is entirely imaginary.

Answer 5: Let us suppose that the bag of M&Ms contains finitely many M&Ms. First, weigh the empty bag of M&Ms. Then alternately draw one M&M and weigh the bag of remaining M&Ms. This gives eleven data points, from which we may estimate the number of M&Ms in the bag. It is unavoidable that we draw 10 M&Ms, so this is all we have drawn. It is entirely reasonable to get the weight of the bag and remaining M&Ms to within 1 part in 1000. (1 part in 100,000 is do-able, but finicky.) Use this to estimate the number of M&Ms originally in the bag -- this is a distribution on the integers. Personal experience weighing real M&Ms indicates that weight has no color dependence and that the variation in individual M&M masses is quite small.

If there is a multiple of 10 that is maximally likely, call that number $10N$, where we take $N$ to be the number of M&Ms of one/each color. Now draw 9N+1 M&Ms. As per answer 2 above, you are guaranteed to have one of each color.

On the other hand, the number of M&Ms may be so large that the small variation in the masses of individual M&Ms admits several multiples of ten as viable counts of the original number of M&Ms. In this case, take the number of viable candidate counts, divide by six (a rough approximation assuming a uniform distribution over these counts; it is conservative in that it leads to drawing slightly more M&Ms than assuming a more concentrated distribution), square that number and multiply by the ten M&Ms we have already drawn, this is an estimate of the total number of M&Ms we must draw to reduce the standard error in the mean of the count of M&Ms to be approximately $\sqrt{10}$, which will be enough narrowing to lead to a single winner for the original number of M&Ms in the bag. A quick estimate shows that this would require something like 300,000 initial M&Ms, which would weigh around 350 kg, or vastly more M&Ms than have ever been sold in a single bag.

Answer 6: Hey interviewer, I'll give you this great bag of M&Ms if you'll tell me how many you draw before you get 10 different colors.

Answer 7: Outsource it to (checks Google for country with most outsourcing) India.

For more on the color distribution, see Wicklin, Rick, The distribution of colors for plain M&M candies, 2017. A related popular article is Purtill, Corinne, A statistician got curious about M&M colors and went on an endearingly geeky quest for answers, 2017.

Answer 4

"Fermi problem" answer:

Nothing in life is certain, so it seems reasonable to ask for a 99% likelihood of having all 10.

Now, the probability of not finding a particular color in $n$ trials is $(9/10)^{n}$. I would think the events of not finding any given color ever are "asymptotically independent" in some sense, so that the probability of not having them all is $$ \begin{split}p&\approx 10 (9/10)^n \\ & \approx 10\mathrm{e}^{-n/10} \\ & \approx 10^{1-n/20}\text{,} \end{split}$$ i.e., $$n\approx 20(\log_{10} \tfrac{1}{p} + 1)$$

so that $n\approx 60$ or so.