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

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

Условие

Император пригласил на праздник 2015 волшебников, добрых и злых, при этом волшебники знают, кто добрый и кто злой, а император – нет. Добрый волшебник всегда говорит правду, а злой говорит что угодно. На празднике император сначала выдаёт каждому волшебнику по бумажке с вопросом (требующим ответа "да" или "нет"), затем волшебники отвечают, и после всех ответов император одного изгоняет. Волшебник выходит в заколдованную дверь, и император узнаёт, добрый он был или злой. После этого император вновь выдаёт каждому из оставшихся волшебников по бумажке с вопросом, вновь одного изгоняет, и так далее, пока император не решит остановиться (это возможно после любого из ответов, и после остановки можно никого не изгонять). Докажите, что император может изгнать всех злых волшебников, удалив при этом не более одного доброго.


Решение

  Первый этап. Император выделяет одного волшебника A и спрашивает всех оставшихся, добрый ли он (а его – о чём угодно). Имеем два случая.
  1) Все сказали "нет". Тогда император изгоняет A. Если оказалось, что A – добрый, то все остальные волшебники – злые, и император изгоняет их по очереди, задавая произвольные вопросы. Если оказалось, что A – злой, то число злых волшебников уменьшилось, и император снова повторяет первый этап.
  2) Нашёлся волшебник B, сказавший "да". Тогда император изгоняет B. Если оказалось, что B – злой, то император также возвращается к первому этапу. Если оказалось, что B – добрый, то император понимает, что A – добрый и переходит ко второму этапу.
  Второй этап. Император ставит волшебников по кругу и спрашивает каждого, добрый ли следующий. Если все ответили "да", то все оставшиеся в зале волшебники – добрые, и император останавливается.
  Если кто-то ответил "нет", то первый, начиная со следующего за A волшебника, про которого так сказали, – злой. Император его изгоняет и возвращается ко второму этапу.

Замечания

10 баллов.

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

олимпиада
Название Турнир городов
Турнир
Номер 36
Дата 2014/15
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 6

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

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