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