variation of Birthday paradox I have a set $S$ of $n$ elements. I select $r$ elements from the set $E_1, E_2, E_3, \ldots, E_r$ that may not be all distinct. I select again $r$ elements from the set $F_1,F_2,F_3,\ldots, F_r$ in a similar manner.
What is the probability $P$ that $E_i = F_j$ for some $i$ and $j$? 
I have to prove that this probability is at least one half of the probability that $2r$ randomly chosen elements selected from $S$ are not all distinct.
 A: The probability $P$ that you're looking for is equal to the probability that among $2r$ randomly chosen elements, at least two whose indices have different parity are equal. Now consider what happens when, instead of just drawing $2r$ elements, you first draw them and then reorder them randomly (using a permutation from $S_{2r}$). Suppose among the first $2r$ elements there was a pair of equal elements; what is the probability that under the new ordering, these find themselves in positions with opposite parity?
A: Take any list of $2r$ elements and randomly permute their order.  Suppose that elements $i$ and $j$ were equal before the shuffle.  After the shuffle, the probability that these elements are in opposite halves of the list (i.e., one is in the first $r$ positions and the other is in the last $r$ positions) is equal to $r/(2r-1)$.  Therefore, given that the original $2r$ elements were not all distinct, the probability that (after shuffling) one of the first $r$ elements is equal to one of the last $r$ elements is at least $r/(2r-1)$ (it is strictly greater if more than one pair of elements is equal).  But this conditional probability is just the ratio that is asked for:
$$
\frac{P\left[\exists_{i,j}E_i=F_j\right]}{P\left[2r\text{ not distinct}\right]} = P\left[\exists_{i,j}E_i=F_j \vert E, F\text{ not all distinct}\right] \ge \frac{r}{2r-1} > \frac{1}{2}.
$$
Note that the size of set $S$ is not used, and neither is the fact that all elements were equally likely.  The inequality holds whenever the elements are independent and identically distributed.
