Муниципалка 10 - 11 класс
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
125 студентов пришли в большую аудиторию. Каждый из студентов знаком ровно с десятью другими. Некоторые из студентов покинули аудиторию во время перерыва. Затем выяснилось, что все оставшиеся студенты знакомы с одинаковым числом людей, оставшихся в аудитории. Докажите, что среди студентов, которые ушли, были знакомые друг с другом.
Источники:
Подсказка 1
Люди и знакомства, да это же графы. А в графах полезно считать кол-во рёбер. Так давайте посчитаем кол-во рёбер до выхода студентов и после. Причём, чтобы получить сильное условие на то, что среди студентов, которые ушли, не было знакомых друг с другом предположим, что факт не верен.
Подсказка 2
Для подсчёта введём обозначения, пусть m - кол-во ушедших студентов, а d - степень каждой из оставшихся вершин. Нам очень повезло, что ушедшие студенты не знакомы друг с другом, ведь тогда каждый забрал с собой по 10 рёбер (если бы они были знакомы, то мы могли случайно выкинуть какое-то ребро дважды).
Подсказка 3
До ухода студентов: 10*125/2 = 625, после: (125-m)*d/2, причём выше мы доказали, что после стало на 10m рёбер меньше. Ура! Мы получили уравнение в целых числах, а раз мы предполагаем, что мы придём к противоречию по итогу, то хотелось бы, чтобы оно не имело целых решений, а ещё мы помним, что часто решений нет из-за проблем с делимостью, может быть тут тоже так?
Подсказка 4
Не забудем, что у нас есть ограничение на d: 0 <= d <= 10, на какую максимальную степень 5 тогда может делиться 20-d?
Подсказка 5
Верно, на первую, тогда остаётся рассмотреть 2 случая: d = 0, d = 5 и в обоих прийти к противоречию.
Первоначально имеем граф с 125 вершинами, причем степень каждой вершины равна 10. Поэтому число всех ребер графа равно
Предположим, что утверждение задачи неверно, то удалось найти 
вершин (студентов), никакие две из которых не
соединены ребром (студенты не знакомы), и при удалении которых вместе с ребрами, из них выходящими (студенты ушли), остается
подграф с 
вершинами, каждая из которых имеет одну и ту же степень 
. В этом новом графе число ребер равно 
, и оно
на 
меньше числа ребер исходного графа (т.к. с каждой удаленной вершиной «исчезают» 10 ребер, выходящих из этой вершины, и все
«исчезающие» ребра различны). Таким образом,
где 
(степень вершин изначально была равна 
). Легко видеть, что 
делится самое большее на первую степень числа
5, поэтому 
делится на 25. Пусть 
Тогда 
. Значит, число 
делится на 5, т.е. либо 
,
либо 
, т.е. либо 
, либо 
, что невозможно при целых значениях 
. Отсюда вытекает, что наше предположение
неверно, значит, утверждение задачи справедливо.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
