Петя завел учётную запись в социальной сети и сходу добавил в

Оценка:

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

Пример:

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

Ответ: 60.