|
|
 |
Условие
На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить "Да" или "Нет" на вопрос: "На острове рыцарей больше, чем лжецов?". Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов "Да" и "Нет" было поровну, давал любой из этих ответов. Оказалось, что ответов "Да" было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова?
Решение
Назовём рыцарей и лжецов приниципиальными людьми.
Оценка. Первый способ. (Бучаев Абдулкадыр) Будем следить за балансом – разностью количеств ответов "Да" и "Нет". В начале и в конце баланс нулевой, с каждым ответом он изменяется на 1. Нулевые значения баланса разбивают ряд жителей на группы. Внутри каждой группы баланс сохраняет знак. Подпевалы всегда увеличивают модуль баланса. Поэтому, чтобы сделать баланс нулевым, принципиальных жителей должно быть не меньше, чем подпевал. Это справедливо для каждой группы, а значит, и для всех жителей острова.
Второй способ. Подпевала не мог увеличивать минимум из текущих количеств "Да" и "Нет". Так как этот минимум увеличился от 0 до 1009, причём с каждым ответом он изменялся не более чем на единицу, то принципиальных жителей хотя бы 1009.
Пример. Сначала все 1009 подпевал сказали "Нет", а потом 1009 рыцарей сказали "Да".
Ответ
1009 подпевал.
Замечания
1. Любой строй из 1009 принципиальных жителей можно проредить подпевалами так, чтобы выполнялось условие.
2. Баллы: 8-9 кл. – 6, 10-11 кл. – 5.
