Vrftjkry

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}cdotfrac{C}{N-1}$

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

Etc...

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

Any ideas? Thank you in advance!

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 $Capprox 4.2$.

Hence, we boldly check the cases $C=4$:
$C=4$ leads to a losing probability of $$frac{96choose 16}{100choose 16}=frac{96!84!}{80!100!}=frac{84cdot 83cdot 82cdot 81}{100cdot 99cdot 98cdot 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 {100cdot 99 cdot 98cdot 97cdot 96cdot 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)}{100cdot 99 cdot 98cdot 97cdot 96cdot 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]

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-Cchoose 16}{100choose 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 $nin{30, 31, cdots, 100}.$

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