Феи и ведьмы
Модераторы: Азарапетыч, Администрация
-
- Писатель на заборах
- Сообщения: 120
- Зарегистрирован: 29 мар 2012, 18:05
Феи и ведьмы
На съезде волшебниц присутствовало k добрых фей и злых ведьм, причём фей было больше, чем ведьм. Известно, что на любой вопрос феи всегда отвечают правду, а ведьмы иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждую волшебницу хочет установить, фея та или ведьма. Для этого он любой волшебнице может задать вопрос: "Кем является такая-то: феей или ведьмой?" (В частности, может спросить, кем является сама эта волшебница.) Доказать, что математик может установить это за 2k − 3 вопросов.
Re: Феи и ведьмы
Если у нас четное число делегатов, то просим одного отойти в сторону, решаем задачу с нечетным числом делегатов, а потом задаем одной из обнаруженных фей вопрос о делегате, стоящем в стороне. В этом случае у нас даже сэкономлен один вопрос.
Для нечетного числа делегатов используем следующий алгоритм.
1. Выстраиваем всех делегатов в затылок.
2. Подходим к самому последнему делегату
3. Спрашиваем, кто стоит перед ним.
4. Если получен ответ "фея", то переходим к тому делегату, о котором только что спрашивали, и возвращаемся к п.3.
5. Если получен ответ "ведьма", то обоих делегатов (и спросившего и того, о ком спрашивали) отводим в сторону, а сами возвращаемся к человеку
Что у нас может остаться в конце?
а) Один делегат, который не задавал вопросов и о котором никто не спрашивал. В этом случае было задано k-2 вопросов. Этот делегат - точно фея и, задав ему еще k-1 вопрос обо всех прочих делегатах, мы узнаем, кто есть кто.
б) Один делегат, который отвечал как минимум на один вопрос. В этом случае он тоже фея и его ответ верный. То есть, был задан k-1 вопрос и понадобится еще максимум k-2.
в) Цепочка из трех или более делегатов. В этой цепочке все отвечали "фея", а значит последние двое в ней - точно феи. И нам опять, наряду с уже заданным k-1 вопросом понадобится еще не более чем k-2, чтобы идентифицировать всех остальных.
Для нечетного числа делегатов используем следующий алгоритм.
1. Выстраиваем всех делегатов в затылок.
2. Подходим к самому последнему делегату
3. Спрашиваем, кто стоит перед ним.
4. Если получен ответ "фея", то переходим к тому делегату, о котором только что спрашивали, и возвращаемся к п.3.
5. Если получен ответ "ведьма", то обоих делегатов (и спросившего и того, о ком спрашивали) отводим в сторону, а сами возвращаемся к человеку
Что у нас может остаться в конце?
а) Один делегат, который не задавал вопросов и о котором никто не спрашивал. В этом случае было задано k-2 вопросов. Этот делегат - точно фея и, задав ему еще k-1 вопрос обо всех прочих делегатах, мы узнаем, кто есть кто.
б) Один делегат, который отвечал как минимум на один вопрос. В этом случае он тоже фея и его ответ верный. То есть, был задан k-1 вопрос и понадобится еще максимум k-2.
в) Цепочка из трех или более делегатов. В этой цепочке все отвечали "фея", а значит последние двое в ней - точно феи. И нам опять, наряду с уже заданным k-1 вопросом понадобится еще не более чем k-2, чтобы идентифицировать всех остальных.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Феи и ведьмы
Я умею это делать за 3/2k вопросов
UPD: Хотя нет, кажется я поторопился.
UPD: Хотя нет, кажется я поторопился.