IMC 2017 · Day 1 · P4

Let $d = 1000$ and let $0 < p < 1$. Choose the set $S$ randomly such that each people is selected with probability $p$, independently from the others.

The probability that a certain person is selected for $S$ and knows exactly two members of $S$ is $$q = \binom{d}{2} p^3 (1 - p)^{d-2}.$$ Choose $p = 3/(d+1)$ (this is the value of $p$ for which $q$ is maximal); then $$\begin{align*} q &= \binom{d}{2} \left( \frac{3}{d+1} \right)^3 \left( \frac{d-2}{d+1} \right)^{d-2} = \\ &= \frac{27 d (d-1)}{2 (d+1)^3} \left( 1 + \frac{3}{d-2} \right)^{-(d-2)} > \frac{27 d (d-1)}{2 (d+1)^3} \cdot e^{-3} > \frac{1}{2017}. \end{align*}$$ Hence, $\mathsf{E} \bigl( |S| \bigr) = nq > \frac{n}{2017}$,

so there is a choice for $S$ when $|S| > \frac{n}{2017}$.