### International Mathematics Competition for University Students

July 31 – August 6 2017, Blagoevgrad, Bulgaria

Home

Ivan is Watching You

Results
Individuals
Teams
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$.
Hint: Choose the set $S$ randomly.