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!
 A: 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]
A: 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).
A: 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.
A: 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).$
