# Selecting unique questions without replacement

I'm trying to create a Q&A game and have a question.

X = number of questions (the question bank) I randomly choose 40 questions from X. A question is chosen with replacement. I want to figure out how many questions I need so that there will be 40 unique questions. In essence, the player can't get the same question twice.

It seems basic to me but I can't figure it out. I was thinking it was a combinations without replacement with (X + 40 -1)/(40! (n-1)), but can't seem to get going from there. Any help would be greatly appreciated. Thanks in advance.

-
I can't quite understand your question. You're saying you choose 40 questions from $X$ , and you want to know how many questions there will have to be in order for you to choose 40 unique questions from $X$? –  Module Mar 7 at 22:17
with replacement, yea. so if you answer question 1, very unlikely (less than 5% chance) that the other 39 questions can be the same as question 1 from X. Sorry I forgot to add the less than 5% chance. –  user2989523 Mar 7 at 22:24

Let $n$ be the number of questions. We are choosing $40$ questions with replacement, so all $n^{40}$ strings of $40$ questions are equally likely.

The number of sequences of $40$ different questions is $n(n-1)(n-2)\cdots (n-39)$. so the probability that all the questions are different is $$\frac{n(n-1)(n-2)\cdots (n-39)}{n^{40}}.\tag{1}$$ We want to make it very unlikely that there is a repetition. Suppose for example that we want the probability of no repetition to be at least $0.99$.

So we want to choose $n$ so that (1) is at least $0.99$. This is a variant of the Birthday Problem. The Wikipedia article has estimates that will let you choose a suitable $n$.

A calculation: In this case, $n$ is very large compared to $40$, so estimates need not be delicate. The logarithm of our probability is $$\log\left(1-\frac{1}{n}\right)+ \log\left(1-\frac{2}{n}\right)+\cdots +\log\left(1-\frac{39}{n}\right).$$ For $x$ close to $0$, we have $\log(1-x)\approx -x$. So want $$-\frac{1}{n}\left(1+2+\cdots +39\right)\approx \ln(0.99).$$ The $n$ that we obtain will be reasonably close to the truth.

Sloppier, but adequate here, is to use the fact that $(n-1)(n-2)\cdots(n-39)$ is not too far away from $(n-20)^{40}$.

Added: In a comment, OP mentions that the desired probability of a duplicate is less than $5\%$. For that, replace the $0.99$ in the answer above by $0.95$.

Each of the suggested approximate calculations yields an answer of about $15200$. Lots of questions!

-