Question

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

Answer 1

Оценка:

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

Пример:

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

Ответ: 60.

Answer 2

Давайте рассмотрим ситуацию шаг за шагом:

1. Петя добавил в друзья 30 человек сразу.
2. Затем он начал добавлять тех, у кого у него есть по крайней мере 30 общих друзей. При этом, все его приглашения сразу принимались.

Поскольку Петя остановился только после того, как у него стало более 5000 друзей, это означает, что у него с Васей, как минимум, 5000 общих друзей.

Теперь рассмотрим минимальное количество общих друзей, которое может быть у Пети и Васи:

• Петя добавил 30 друзей сразу, и это, следовательно, его начальное количество друзей (до добавления тех, у кого 30 общих друзей).
• Затем он добавил остальных друзей до тех пор, пока их количество не превысило 5000.
• Поскольку у Пети с Васей больше всего общих друзей, они обязательно добавляли друг друга в друзья.

Теперь давайте предположим, что у Пети и Васи ровно 5000 общих друзей. Это означает, что после добавления первых 30 друзей, каждый следующий человек, которого они добавили, также добавил им общих друзей.

• 1-й друг: +30 общих друзей (итого 30)
• 2-й друг: +1 общий друг (итого 31)
• 3-й друг: +1 общий друг (итого 32)
• ...
• 5000-й друг: +1 общий друг (итого 5000)

Теперь у Пети и Васи по 5000 общих друзей, и это минимально возможное количество общих друзей, какое может быть у них в данной ситуации.