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