Finding best strategy to open a lock Suppose you have a 4-digit combination lock, but you have forgotten
the correct combination. Consider the following three strategies to find
the correct one:
(i) Try the combinations consecutively from 0000 to 9999.
(ii) Try combinations using simple random sampling with replacement from the set of all possible combinations.
(iii) Try combinations using simple random sampling without replacement from the set of all possible combinations.
Assume that the true combination was chosen uniformly at random
from all possible combinations. Determine the expected number of
attempts needed to find the correct combination in all three cases.
Case 1. Expected no of attempts is $\sum_{k=0}^{9999} k \frac 1{10000}$ as $P(X= k) = \frac 1{10000}$ giving 5000 as answer which appears to be true intuitively.
Case 2 appears to be case of expected no of trials for first success with $p= \frac 1{10000}$
Rest I have no idea. Any help would be appreciated.
Question is from entrance exam and approximate time on question is 10-15 min with no calculators.
 A: Your answer in case $1$ is slightly wrong.  The summation limits should run from $1$ to $10,000$ not $0$ t0 $9,999$ giving the answer $5,000.5.$  Afetr all, you can never open the lock in $0$ tries, and it's possible that it will take $10,000$ if you're really unlucky.
In case $2$, you have a geometric distribution with probability of success $p={1\over10000}$ as you said.  The expected number of trials until the first success is $\frac1p=10,000.$
You should approach case $3$ like case $1$.  The expected number of trials is $\sum_{k=1}^{10000}p_kk$ where $p_k$ is the probability that you succeed on the $k$th trial.  It's perhaps easier to calculate $1-p_k.$  This is the probability that the first $k$ numbers you choose are wrong.  This is $$1-p_k={{9999\choose k}\over{10000\choose k}}={10000-k\over10000}\implies p_k={k\over10000}$$ because we choose $k$ out of the $9999$ wrong numbers, and there are ${10000\choose k}$ ways to choose $k$ numbers without replacement.
The answer in case $3$ is therefore the same as the answer in case $1.$  Testing deterministically is no better of worse than sampling randomly without replacement, in this instance.
As Ross Millikan has pointed out in a comment, it is intuitively clear that the first and third methods should give the same expectation, because you are just trying the combinations in a different order.  The expectation doesn't change whether the order is determined randomly or deterministically. 
