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