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