Некоторые из жителей далёкого острова – добрые волшебники, а некоторые – злые колдуны. Всё, что говорит добрый волшебник, становится правдой, а всё, что говорит злой колдун – перестаёт быть правдой (посредством превращения волшебников в колдунов и наоборот). Королевский инквизитор поймал троих чародеев, но не знает ни про кого из них, является ли он волшебником или колдуном. Инквизитор может заставить каждого из чародеев тыкнуть пальцем на другого чародея и назвать его волшебником, назвать его колдуном, сказать, что он такой же чародей, как и третий чародей, либо, что он отличается от третьего чародея (в последних двух случаях превращается второй чародей). Может ли инквизитор добиться, чтобы все чародеи стали добрыми волшебниками, и если да, какое наименьшее количество приказов ему потребуется?

Да, инквизитор может добиться, чтобы все трое стали добрыми волшебниками. Минимально нужно 4 приказа.

Обозначим чародеев как \( A \), \( B \), \( C \).

• 1. Заставить \( A \) указать на \( B \) и сказать: «\( B \) — волшебник». После этого \( B \) станет таким же, как \( A \).
• 2. Заставить \( A \) указать на \( C \) и сказать: «\( C \) такой же, как \( B \)». Так как после первого приказа \( A \) и \( B \) одинаковые, \( C \) обязательно станет добрым волшебником.
• 3. Теперь \( C \) точно добрый. Заставить \( C \) указать на \( A \) и сказать: «\( A \) — волшебник». Тогда \( A \) станет волшебником.
• 4. Заставить \( C \) указать на \( B \) и сказать: «\( B \) — волшебник». Тогда \( B \) тоже станет волшебником.

Почему меньше нельзя: одним приказом можно изменить состояние только одного чародея. Сначала инквизитор не знает, кто добрый, поэтому за первые два приказа можно лишь гарантированно получить одного точно доброго волшебника. Потом ещё двумя приказами он делает добрыми двух оставшихся. Значит, нужно не меньше четырёх приказов, и 4 действительно хватает.

0 0 Пожаловаться