Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 0 down vote accepted

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.