International Mathematics Competition for University StudentsJuly 31 – August 6 2017, Blagoevgrad, Bulgaria  
Day 1
Day 2
Results
Download

Problem 44. 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 (1p)^{d2}. $$ 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{d2}{d+1}\right)^{d2} = $$ $$ = \frac{27d(d1)}{2(d+1)^3} \left(1+\frac3{d2}\right)^{(d2)} > \frac{27d(d1)}{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}$. 