Оценка + пример
Ошибка.
Попробуйте повторить позже
В беседе курса “Боталка” 1337 участников. У каждого из них не больше трёх друзей. Дмитрий Алексеевич узнал, кто с кем дружит, и теперь хочет разбить одну беседу на несколько. Если два друга оказываются в одной беседе, то они немедленно начинают спамить. Какое наименьшее количество бесед нужно создать, чтобы спам прекратился (то есть любые два друга оказались в разных беседах)?
Подсказка 1
В данной задаче стоит начать с оценки снизу, то есть подумать, сколько минимум может быть бесед. Как думаете, скольких бесед точно не хватит, чтобы рассадить компанию из четырёх людей, в которой каждый знает каждого?
Подсказка 2
По принципу Дирихле, если мы возьмём три беседы, то в одной из них окажется не менее двух друзей, значит, три беседы будет недостаточно. Подумайте, получится ли распределить всех участников Боталки по четырём беседам, чтобы ни в одной из них не нашлось двух друзей!
Меньше четырёх бесед не хватит, ведь в соответствии с условием задачи могут найтись такие четыре ботальщика, что каждый из них знает
остальных трёх (то есть каждый человек дружит с остальными тремя). Эту компанию друзей нужно рассадить по разным беседам.
Очевидно, для них не хватит 
(или меньше) бесед, поскольку в какой-то окажутся двое и начнут спамить стикерами и флудить на не
связанные с обсуждением задач темы.
На 
беседы разделить ребят можно. Для этого Дмитрий Алексеевич может последовательно выбирать человека и смотреть на текущие
списки людей из бесед. У каждого ботальщика не больше трёх друзей, поэтому есть не больше трёх бесед, в которых уже находятся друзья
рассматриваемого человека. Значит, есть хотя бы одна беседа, в которой ботальщик пока никого не знает. Туда его и надо поместить (при
наличии нескольких таких бесед можно выбрать любую).
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
