Ответы на вопрос:
оценка:
предположим, что удалось сделать так, чтобы общих друзей у васи и пети было 59 или меньше. построим ориентированный граф, где вершины - друзья пети (без пети), а рёбра - знакомства. граф будем строить поэтапно. первые 30 вершин - первые 30 друзей пети. от каждого из них может выходить до 59 рёбер с направлением "от них" (знакомства) (иначе найдётся друг пети, у которого хотя бы 60 общих с петей друзей). в любую добавляемую вершину должно указывать не менее 30 рёбер, но исходить из неё при этом может не больше 29 рёбер (иначе противоречие к условию). значит, из первых 30 вершин вышло не более 1770 рёбер, а после добавления каждой из последующих вершин количество "свободных" рёбер уменьшается хотя бы на 1. так как нужно добавить ещё хотя бы 4971 вершину, рёбер просто не хватит. противоречие.
пример:
пусть сначала петя познакомился с 30 людьми (между собой не дружат), каждый из которых был знаком ещё ровно с 30 людьми (одними и теми же) (которые тоже попарно не дружат между собой). когда петя перезнакомился со всеми новыми 30 людьми, оказалось, что каждый из них знает ещё ровно по 30 человек, снова попарно не дружащих между собой (опять одни и те же 30 человек). и так в итоге, у каждого из друзей пети не больше 60 общих с ним друзей.
ответ: 60.
Реши свою проблему, спроси otvet5GPT
-
Быстро
Мгновенный ответ на твой вопрос -
Точно
Бот обладает знаниями во всех сферах -
Бесплатно
Задай вопрос и получи ответ бесплатно
Популярно: Математика
-
Мотылёк6212.03.2020 06:44
-
джопер27.12.2020 20:14
-
Александра89431205.05.2022 06:28
-
ab198me04.06.2021 13:14
-
ekaterinaf7908.07.2020 07:06
-
olegykoleg09.07.2020 06:38
-
veronkagavrily18.07.2020 19:09
-
nataliamakarov326.07.2020 13:27
-
lyubimov2005118.06.2021 04:25
-
LutsenkoRodion14.04.2020 22:02
Есть вопросы?
-
Как otvet5GPT работает?
otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса. -
Сколько это стоит?
Проект находиться на стадии тестирования и все услуги бесплатны. -
Могу ли я использовать otvet5GPT в школе?
Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое! -
В чем отличия от ChatGPT?
otvet5GPT черпает академические источники из собственной базы данных и предназначен специально для студентов. otvet5GPT также адаптируется к вашему стилю письма, предоставляя ряд образовательных инструментов, предназначенных для улучшения обучения.