На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить «Да» или «Нет» на вопрос: «На острове рыцарей больше, чем лжецов?». Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов «Да» и «Нет» было поровну, давал любой из этих ответов. Оказалось, что ответов «Да» было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова?
Назовём рыцарей и лжецов принципиальными людьми.
Оценка. Приведём решение Бучаева Абдулкадыра.
Будем следить за балансом — разностью количеств ответов «Да» и «Нет». В начале и в конце баланс нулевой, с каждым ответом он изменяется на 1. Нулевые значения баланса разбивают ряд жителей на группы. Внутри каждой группы баланс coxраняет знак. Подпевалы всегда увеличивают модуль баланса. Поэтому, чтобы сделать баланс нулевым, принципиальных жителей должно быть не меньше чем подпевал. Это справедливо для каждой группы, а значит, и для всех жителей острова.
Ответ: 1009 подпевал.
Приведём другое решение.
Подпевала не мог увеличивать минимум из текущих количеств «Да» и «Нет». Так как этот минимум увеличился от 0 до 1009, причём с каждым ответом он изменялся не более чем на единицу, то принципиальных жителей хотя бы 1009.
Пример. Сначала все 1009 подпевал сказали «Нет», а потом 1009 рыцарей сказали «Да».
Замечание.
Любой строй из 1009 принципиальных жителей можно проредить подпевалами так, чтобы выполнялось условие.