На острове Лжецов и Рыцарей расстановку по кругу называют правильной, если каждый, стоящий в кругу, может сказать, что среди двух его соседей есть представитель его племени. Однажды 2019 аборигенов образовали правильную расстановку по кругу. К ним подошел лжец и сказал: «Теперь мы вместе тоже можем образовать правильную расстановку по кругу». Сколько рыцарей могло быть в исходной расстановке?
спросил 25 Ноя, 19 от полька в категории школьный раздел


решение вопроса

+6
Ответ: 1346.
Решение. Докажем, что правильная расстановка по кругу возможна тогда и только тогда, когда рыцарей, по крайней мере, в два раза больше, чем лжецов. Действительно, из условия задачи следует, что в такой расстановке соседями каждого лжеца являются два рыцаря, а среди соседей любого рыцаря есть хотя бы один рыцарь. Тогда правильная расстановка должна выглядеть так: группа рыцарей, лжец, группа рыцарей, лжец, и так далее (в каждой группе не менее двух рыцарей). Значит, при такой расстановке рыцарей хотя бы в два раза больше, чем лжецов. В обратную сторону: если рыцарей в два раза больше, чем лжецов, то делаем расстановку вида РРЛРРЛ..., а оставшихся рыцарей (если они есть) помещаем между любыми двумя рыцарями. Таким образом, если выполняется такое условие, то правильная расстановка возможна.
Пусть в правильной расстановке, указанной в условии, стоят Р рыцарей и Л лжецов, тогда Р ≥ 2Л. Подошедший лжец сказал неправду, поэтому вместе с ним правильная расстановка невозможна, следовательно, Р ≤ 2Л + 1. Таким, образом Р = 2Л или Р = 2Л + 1. В первом случае, в исходной расстановке 2019⋅ 2/3 = 1346  рыцарей, а второй случай невозможен, так как число (2019 -1) * 2/3  не будет целым.
ответил 25 Ноя, 19 от олейчик

Связанных вопросов не найдено

Обучайтесь и развивайтесь всесторонне вместе с нами, делитесь знаниями и накопленным опытом, расширяйте границы знаний и ваших умений.

Популярное на сайте:

Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах. 

Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте. 

Как быстро и эффективно исправить почерк?  Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.

Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.