International Mathematics Competition for University Students

July 31 – August 6 2017, Blagoevgrad, Bulgaria

Home

Ivan is Watching You

Day 1
    Problem 1
    Problem 2
    Problem 3
    Problem 4
    Problem 5

Day 2
    Problem 6
    Problem 7
    Problem 8
    Problem 9
    Problem 10

Results
    Individuals
    Teams
    Leaders

Download
    Day 1 questions
    Day 1 solutions
    Day 2 questions
    Day 2 solutions
    Closing Ceremony
        Presentation

Official IMC site

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