на острове лжецов и рыцарей расстановку по кругу называют правильной, если каждый, стоящий в кругу, может сказать, что среди двух его соседей есть представитель его племени. Однажды, 2019 аборигенов образовали правильную расстановку по кругу. к ним подошел лжец и сказал: "теперь мы вместе тоже сможем образовать правильную расстановку по кругу". сколько рыцарей могло быть в исходной расстановке?
More Questions From This User See All
Answers & Comments
Ответ: 1346.
Пошаговое объяснение: Докажем, что правильная расстановка по кругу возможна тогда и только
тогда, когда рыцарей, по крайней мере, в два раза больше, чем лжецов.
Действительно, из условия задачи следует, что в такой расстановке соседями
каждого лжеца являются два рыцаря, а среди соседей любого рыцаря есть хотя бы один
рыцарь. Тогда правильная расстановка должна выглядеть так: группа рыцарей, лжец,
группа рыцарей, лжец, и так далее (в каждой группе не менее двух рыцарей). Значит, при
такой расстановке рыцарей хотя бы в два раза больше, чем лжецов.
В обратную сторону: если рыцарей в два раза больше, чем лжецов, то делаем
расстановку вида РРЛРРЛ..., а оставшихся рыцарей (если они есть) помещаем между
любыми двумя рыцарями. Таким образом, если выполняется такое условие, то
правильная расстановка возможна.
Пусть в правильной расстановке, указанной в условии, стоят Р рыцарей и Л лжецов,
тогда Р больше либо равно 2Л. Подошедший лжец сказал неправду, поэтому вместе с ним правильная
расстановка невозможна, следовательно, Р меньше либо равно 2Л + 1.
Таким, образом Р = 2Л или Р = 2Л +
1. В первом случае, в исходной расстановке 2019*2/3
= 1346 рыцарей, а второй случай
невозможен, так как число (2019 – 1)*2/3
не будет целым.