Suppose that Alice has a fair die with N sides, labelled 1..N. Only Alice knows N, and Alice won't tell N to anyone else.

However, you may ask Alice to toss the die, and then she'll tell you which side came up. You may repeat asking Alice to toss the die as finitely many times as you want.

Can you devise an algorithm, which infers N with probability at least 99%?

One possible direction (or maybe not):

1. Let X be a random variable, which counts the number of tosses until any side comes up twice.

2. Compute the expected value of X in terms of the unknown N.

3. Toss the die until some side comes up twice, let Y be the actual number of tosses.

4. Using some probabilistic bound (e.g. Markov inequality), deduce how many more tosses are needed in order to infer N with probability at least 99%.

I'd be happy to develop this idea to a proven algorithm, or devise some other proven algorithm.

Thanks.