Good evening. I would like to show the following statement :
Let $n>1$, and $E,F$ two subsets of $[\![ 1,n ]\!]$ randomly and independently chosen such that $|E| = |F| = \lfloor\sqrt{ n }\rfloor + 1$. We have : $$\mathbb{P}(E \cap F \neq \varnothing) \geqslant 1 - e^{-\frac{7}{10}}$$
I tried to used the logarithm, i tried to use the convexity inequality $1-x \leqslant e^{-x}$ (true for every real numbers), but nothing worked. I didn't tried $\ln(1-x) \leqslant -x$ for the moment.
Why $e^{-\frac{7}{10}}$ is here ?!
The text says that this is a rewording of birthday paradox, I don't even see why.
My biggest attempt :
Proof : It is equivalent to show that : $$\mathbb{P}(E \cap F = \varnothing) \leqslant e^{-\frac{7}{10}}$$
Let $k := \lfloor \sqrt{n} \rfloor + 1$. Without loss of genrality we can suppose that $E = [\![1, k ]\!]$. We have : $$\mathbb{P}(E \cap F = \varnothing) = \frac{\binom{n-k}{k}}{\binom{n}{k}} = \frac{(n-k)! (n-k)!}{n! (n-2k)!} = \frac{(n-k) \dots (n-2k+1)}{n(n-1) \dots (n-k+1)}$$
We see that :
$\displaystyle\frac{n-k}{n} = 1 - \displaystyle\frac{k}{n} \leqslant e^{-\frac{k}{n}}$
$\displaystyle\frac{n-k-1}{n-1} = 1 - \displaystyle\frac{k}{n-1} \leqslant e^{-\frac{k}{n-1}}$
$\dots$
$\displaystyle\frac{n-2k+1}{n-k+1} = 1 - \displaystyle\frac{k}{n-k+1} \leqslant e^{-\frac{k}{n-k+1}}$
Thus : $$\mathbb{P}(E \cap F = \varnothing) \leqslant \prod\limits_{i=0}^{k-1} e^{-\frac{k}{n-i}} = e^{-k\sum\limits_{i=0}^{k-1} \frac{1}{n-i}}$$
As a consequence : $$\mathbb{P}(E \cap F = \varnothing) \leqslant e^{-(\lfloor \sqrt{n} \rfloor + 1) \sum\limits_{i=0}^{\lfloor \sqrt{n} \rfloor} \frac{1}{n-i}}$$
Can I say that : $$\sum\limits_{i=0}^{\lfloor \sqrt{n} \rfloor} \frac{1}{n-i} \leqslant \int_0^{\lfloor \sqrt{n} \rfloor + 1} \frac{\mathrm{d}x}{n-x} = \ln\left| \frac{n}{n -\lfloor \sqrt{n} \rfloor -1 } \right|$$
And then work with that or it's totally illegal.
