Задача 65888

Тема:    [ Теория алгоритмов (прочее) ]

Сложность: 3+ Классы: 5,6

Условие

Иван Царевич хочет выйти из круглой комнаты с шестью дверями, пять из которых заперты на ключ. За одну попытку он может проверить три любые двери, и если одна из них не заперта, то он в неё выйдет. После каждой попытки Баба-Яга запирает дверь, которая была открыта, и отпирает одну из соседних дверей. Какую именно, Иван Царевич не знает. Как ему действовать, чтобы наверняка выйти из комнаты?

Решение

Раскрасим двери в чёрный и белый цвета, чередуя их. Первой попыткой Иван Царевич проверяет все белые двери. Если после этого он не сумел выйти из комнаты, то отперта была чёрная дверь. Баба-Яга её запрёт и отопрёт соседнюю белую. В этом случае Ивану Царевичу достаточно ещё раз проверить все белые двери.

Замечания

Ср. с задачей 65893.

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

олимпиада
Название	Окружная олимпиада (Москва)
год
Год	2016
класс
Класс	5
задача
Номер	5.5