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