uniolympiads Ελληνικά

IMC 2017, Day 1, Problem 4

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

Original from the official PDFThere 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 .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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

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

The probability that a certain person is selected for SS and knows exactly two members of SS is

q=(d2)p3(1−p)d−2.q = \binom{d}{2} p^3(1-p)^{d-2}.

Choose p=3/(d+1)p = 3/(d+1) (this is the value of pp for which qq is maximal); then

q=(d2)(3d+1)3(d−2d+1)d−2==27d(d−1)2(d+1)3(1+3d−2)−(d−2)>27d(d−1)2(d+1)3⋅e−3>12017.\begin{aligned} q &= \binom{d}{2}\left(\frac{3}{d+1}\right)^3\left(\frac{d-2}{d+1}\right)^{d-2} = \\ &= \frac{27d(d-1)}{2(d+1)^3}\left(1+\frac{3}{d-2}\right)^{-(d-2)} > \frac{27d(d-1)}{2(d+1)^3}\cdot e^{-3} > \frac{1}{2017}. \end{aligned}

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

Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?