ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66722
Темы:    [ Математическая логика (прочее) ]
[ Инварианты и полуинварианты (прочее) ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

На острове живут рыцари, лжецы и подпевалы; каждый знает про всех, кто из них кто. В ряд построили всех 2018 жителей острова и попросили каждого ответить «Да» или «Нет» на вопрос: «На острове рыцарей больше, чем лжецов?». Жители отвечали по очереди и так, что их слышали остальные. Рыцари отвечали правду, лжецы лгали. Каждый подпевала отвечал так же, как большинство ответивших до него, а если ответов «Да» и «Нет» было поровну, давал любой из этих ответов. Оказалось, что ответов «Да» было ровно 1009. Какое наибольшее число подпевал могло быть среди жителей острова?

Решение

Назовём рыцарей и лжецов приниципиальными людьми.

Оценка.

Первый способ. (Бучаев Абдулкадыр)

Будем следить за балансом — разностью количеств ответов «Да» и «Нет». В начале и в конце баланс нулевой, с каждым ответом он изменяется на 1. Нулевые значения баланса разбивают ряд жителей на группы. Внутри каждой группы баланс сохраняет знак. Подпевалы всегда увеличивают модуль баланса. Поэтому, чтобы сделать баланс нулевым, принципиальных жителей должно быть не меньше чем подпевал. Это справедливо для каждой группы, а значит, и для всех жителей острова.

Второй способ.

Подпевала не мог увеличивать минимум из текущих количеств «Да» и «Нет». Так как этот минимум увеличился от 0 до 1009, (причём с каждым ответом он изменялся не более чем на единицу, то принципиальных жителей хотя бы 1009.

Пример.

Сначала все 1009 подпевал сказали «Нет», а потом 1009 рыцарей сказали «Да».

Замечание. Любой строй из 1009 принципиальных жителей можно проредить подпевалами так, чтобы выполнялось условие.

Ответ

1009 подпевал.

Источники и прецеденты использования

олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 2
олимпиада
Название Турнир городов
номер/год
Дата 2018/19
Номер 40
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .