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