# I have 100 boxes. C of them have a gift. I can open up to 16 boxes. What is the number of C that will give me probability over 0.5 to find a gift?

Details: We start by opening a box. If nothing is in there, we open another one. Once we find a gift, we can stop. Each empty box that was opened is discarded (no revisit). I can find the number of $$C$$ that will give probability over $$0.5$$ by writing a program to try for $$C=1, C=2$$ .. etc.. , but I can't solve the equation for $$C$$ to find a more "mathematical" and elegant answer.

My work until now is:

1) Found in 1st box: $$P(1) = \frac{C}{N}$$

2) Found in 2nd box: $$P(2) = \frac{1-C}{N}\cdot\frac{C}{N-1}$$

4) Found in 3rd box: $$P(3) = \frac{1-C}{N}\cdot\frac{1-C/}{N-1}\cdot\frac{C}{N-2}$$

Etc...

Adding them up makes things very complicated to solve for $$C$$.

Any ideas? Thank you in advance!

• There are $\binom {100}6$ ways to choose $6$ boxes. How many ways are there to choose $6$ empty boxes? – lulu Nov 18 at 12:39
• Thanks for your response lulu! I do know that, but still it can not be solved for C. Again, this approach will require to try for consecutive values of C in order to find the needed value. Thanks though! :) – XuUserAC Nov 18 at 12:42
• Should the question in the title really be "What is the the minimum number of C..."? – Randall Stewart Nov 18 at 20:04
• This kind of sounds like a software developer’s question about how to rig their game’s loot boxes. – Josh Detwiler Nov 19 at 4:05
• I wouldnt bother opening them. They are all sweaters. – Keltari Nov 19 at 8:51

Start with a rough estimate: If the box contents were independent, the probability of losing would be $$(1-C/100)^{16}$$. Equating this to $$0.5$$ gives us $$C\approx 4.2$$.

Hence, we boldly check the cases $$C=4$$: $$C=4$$ leads to a losing probability of $$\frac{96\choose 16}{100\choose 16}=\frac{96!84!}{80!100!}=\frac{84\cdot 83\cdot 82\cdot 81}{100\cdot 99\cdot 98\cdot 97}\approx 0.492$$ so a winning probability slightly above $$\frac12$$. A close look reveals that $$C=3$$ leads to a winning probability below $$\frac12$$, so the correct answer is $$C=4$$.

Note that the "true" breaking point is thus between $$3$$ and $$4$$, not between $$4$$ and $$5$$ as the rough estimate suggested - the box contents are not independent after all (namely, if you find a - rare - gift, the probability of finding a gift in another box falls dramatically).

As pointed out in the comments, finding the chance of not getting a gift is rather easier, though the patterns involved assist with the computation. Suppose we had six, rather than sixteen, to choose. We have $$\binom {100}{6}=\frac {100!}{6!94!}=\frac {100\cdot 99 \cdot 98\cdot 97\cdot 96\cdot 95}{6!}$$ ways of choosing six boxes, and $$\binom {100-C}{6}=\frac {(100-C)\cdot (99-C) \cdot (98-C)\cdot (97-C)\cdot (96-C)\cdot (95-C)}{6!}$$ ways of choosing six empty ones, so the probability of an empty box is $$p=\frac {(100-C)\cdot (99-C) \cdot (98-C)\cdot (97-C)\cdot (96-C)\cdot (95-C)}{100\cdot 99 \cdot 98\cdot 97\cdot 96\cdot 95}$$

Now setting this equal to $$0.5$$ we get a sextic for $$C$$. The numerator is monotone in $$C$$ so we know that trial can work. Can we do better? Well if we take $$q=\frac {98-C}{98}$$ we can estimate the probability as $$p=q^6$$, and that gives us a potential starting place for trial to reduce the amount of effort involved.

[I see there is another solution which works with a simpler, but slightly different, estimate]

• Given the symmetry, isn't $q=\frac {97.5-C}{97.5}$ an even better approximation? Then $C \approx 97.5(1-q)$ . Also, might as well develop the full expression for 16, not 6. – smci Nov 19 at 10:45
• @smci Yes indeed. At the time I was writing this there was not much in the way of answer and discussion, so I didn't give a direct answer to the question which was being asked, but rather an indication of how to go about it, so that the person who asked the question would have to think about it a little more. Also there was an original focus on integers. But both your suggestions are good. – Mark Bennet Nov 19 at 14:31
• And since there were 16 boxes not 6, the arithmetic midpoint would be 92.5 – smci Nov 19 at 14:42

As with a lot of binomial problems, the easiest way to calculate the probability of success from N tries is to start by calculating the probability of N failures and subtracting the answer from 1.

The probability of opening 16 empty boxes (and thus failing to find a prize) in this case is:

$$\frac{100-C\choose 16}{100\choose 16} = \frac{(100-C)!}{16!(84-C)!}\frac{16!84!}{100!} = \frac{(100-C)!84!}{100!(84-C)!} = \frac{84×83×...×(85-C)}{100×99×...×(101-C)} = \frac{84}{100}×\frac{83}{99}×...×\frac{85-C}{101-C}$$

At this point we can proceed by trial and error multiplying by one term at a time.

For C=1 we get $$\frac{84}{100}$$ which is clearly $$>\frac{1}{2}$$

For C=2, $$\frac{84}{100}×\frac{83}{99}=\frac{6972}{9900} \approx 0.704$$

For C=3, $$\frac{6972}{9900}×\frac{82}{98} \approx 0.589$$

For C=4, $$0.589...×\frac{81}{97} \approx 0.492$$

So the minimum C for which the probability of losing drops below 0.5 (and thus the winning probability is above 0.5) is 4.

An alternative approach is to work in base 10 logarithms. Chance of failing on 16 tries is

$$\displaystyle f(C) = \left(\frac{100-C}{100}\right) \times \left(\frac{99-C}{99}\right) \times \left(\frac{98-C}{98}\right) \times \cdots \times \left(\frac{85-C}{85}\right).$$

Assume that you've written a computer program that calculates $$\;\log_{10}n\;$$ for $$n\in\{30, 31, \cdots, 100\}.$$

Then it becomes a simple matter to calculate $$\;g(C) = \log_{10}f(C).$$