International Mathematics Competition
for University Students
2017

IMC2017: Day 1, Problem 4

4. There are $n$ people in a city, and each of them has exactly $1000$ friends (friendship is always symmetric). Prove that it is possible to select a group $S$ of people such that at least $n/2017$ persons in $S$ have exactly two friends in $S$.

Proposed by: Rooholah Majdodin and Fedor Petrov, St. Petersburg State University

Solution. 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 $$ q = \binom{d}{2} \left(\frac3{d+1}\right)^3 \left(\frac{d-2}{d+1}\right)^{d-2} = $$ $$ = \frac{27d(d-1)}{2(d+1)^3} \left(1+\frac3{d-2}\right)^{-(d-2)} > \frac{27d(d-1)}{2(d+1)^3} \cdot e^{-3} > \frac1{2017}. $$

Hence, $E\big(|S|\big) = nq > \frac{n}{2017}$, so there is a choice for $S$ when $|S|>\frac{n}{2017}$.

Discussion on ArtOfProblemSolving.com