To make the problem slightly more general, take two samples of size √n from a population of size n where n is large.
The probability of no overlap in the two samples is approximately 1/e.
That is, in the limit as n approaches infinity, the probability converges to 1/e.
For n = 1,000,000 the approximation is good to three figures.
This problem is reminiscent of the birthday problem, but it’s a little different because the samples are draw without replacement.
*** [1] The statement of the problem and solution are simple.
The proof is not as simple.
.