В городе N

[Alexander Evnin]

В городе N у любых двух жителей есть общий знакомый. Докажите,
что можно составить городскую Думу из не более чем $\sqrt{1+n\ln n}$ людей
(где $n$ - количество жителей в N) так, что любой житель города, не вошедший
в Думу, имеет хотя бы одного знакомого думца.

Попробуйте уменьшить оценку!