Петя завел учётную запись в социальной сети и сразу добавил в друзья 30 человек. После этого он стал последовательно добавлять каждого, с кем у него есть по крайней мере 30 общих друзей, и остановился лишь тогда, когда друзей стало более 5000 (все петины приглашения сразу принимались). После этого он обнаружил, что больше всего общих друзей у него с Васей. (Возможно, с кем-то еще у Пети оказалось столько же, но не больше, общих друзей, сколько с Васей.) Какое минимальное количество общих друзей может оказаться у Пети и Васи?

Оценка:

Предположим, что удалось сделать так, чтобы общих друзей у Васи и Пети было 59 или меньше. Построим ориентированный граф, где вершины - друзья Пети (без Пети), а рёбра - знакомства. Граф будем строить поэтапно. Первые 30 вершин - первые 30 друзей Пети. От каждого из них может выходить до 59 рёбер с направлением "от них" (знакомства) (иначе найдётся друг Пети, у которого хотя бы 60 общих с Петей друзей). В любую добавляемую вершину должно указывать не менее 30 рёбер, но исходить из неё при этом может не больше 29 рёбер (иначе противоречие к условию). Значит, из первых 30 вершин вышло не более 1770 рёбер, а после добавления каждой из последующих вершин количество "свободных" рёбер уменьшается хотя бы на 1. Так как нужно добавить ещё хотя бы 4971 вершину, рёбер просто не хватит. Противоречие.

Пример:

Пусть сначала Петя познакомился с 30 людьми (между собой не дружат), каждый из которых был знаком ещё ровно с 30 людьми (одними и теми же) (которые тоже попарно не дружат между собой). Когда Петя перезнакомился со всеми новыми 30 людьми, оказалось, что каждый из них знает ещё ровно по 30 человек, снова попарно не дружащих между собой (опять одни и те же 30 человек). И так далее... В итоге, у каждого из друзей Пети не больше 60 общих с ним друзей.

Ответ: 60.