Belarusian Mathematical Olympiad

Answer : $k=2016$. We show that $k\ge 2016$. Note that Borya and Masha together have more friends than Borya and Zhenya, since Zhenya has the least number of friends among all users of the social network. So Borya and Masha together have at least $2017$ friends, and except Borya and Masha there are in total $2016$ people registered in the network. Therefore either Borya and Masha are friends or Borya and Masha have a common friend, say Pavel. Similarly either Anya and Borya are friends or Anya and Borya have a common friend, say, Igor. Thus, Anya can send greetings to Masha with the help of no more than three other network users.

Now we show that no $k\le 2015$ is enough. Let $k=2015$. Let Borya friends with everyone except Masha, Vasya and Gena, while Masha, Vasya and Gena are friends with each other. Zhenya has the only friend Borya. And all users, except Masha, Vasya, Gena and Zhenya are friends with each other. No one else is friends with anyone. Then Borya and Zhenya have $2015\ge k$ friends together, and all other users have less friends than Borya, and more than Zhenya. However, Anya will not be able to send greetings to Masha, since the three users: Masha, Vasya and Gena do not contact the other users. Similarly we can construct the examples for all $1\le k\le 2014$.