Феи и ведьмы

Логические задачи

Модераторы: Азарапетыч, Администрация

Ответить
Петр Иванович Д.
Писатель на заборах
Писатель на заборах
Сообщения: 120
Зарегистрирован: 29 мар 2012, 18:05

Феи и ведьмы

Сообщение Петр Иванович Д. »

На съезде волшебниц присутствовало k добрых фей и злых ведьм, причём фей было больше, чем ведьм. Известно, что на любой вопрос феи всегда отвечают правду, а ведьмы иногда говорят правду, а иногда лгут. Оказавшийся на конференции математик про каждую волшебницу хочет установить, фея та или ведьма. Для этого он любой волшебнице может задать вопрос: "Кем является такая-то: феей или ведьмой?" (В частности, может спросить, кем является сама эта волшебница.) Доказать, что математик может установить это за 2k − 3 вопросов.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Феи и ведьмы

Сообщение Юляша »

Если у нас четное число делегатов, то просим одного отойти в сторону, решаем задачу с нечетным числом делегатов, а потом задаем одной из обнаруженных фей вопрос о делегате, стоящем в стороне. В этом случае у нас даже сэкономлен один вопрос.

Для нечетного числа делегатов используем следующий алгоритм.

1. Выстраиваем всех делегатов в затылок.

2. Подходим к самому последнему делегату

3. Спрашиваем, кто стоит перед ним.

4. Если получен ответ "фея", то переходим к тому делегату, о котором только что спрашивали, и возвращаемся к п.3.

5. Если получен ответ "ведьма", то обоих делегатов (и спросившего и того, о ком спрашивали) отводим в сторону, а сами возвращаемся к человеку

Что у нас может остаться в конце?

а) Один делегат, который не задавал вопросов и о котором никто не спрашивал. В этом случае было задано k-2 вопросов. Этот делегат - точно фея и, задав ему еще k-1 вопрос обо всех прочих делегатах, мы узнаем, кто есть кто.

б) Один делегат, который отвечал как минимум на один вопрос. В этом случае он тоже фея и его ответ верный. То есть, был задан k-1 вопрос и понадобится еще максимум k-2.

в) Цепочка из трех или более делегатов. В этой цепочке все отвечали "фея", а значит последние двое в ней - точно феи. И нам опять, наряду с уже заданным k-1 вопросом понадобится еще не более чем k-2, чтобы идентифицировать всех остальных.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Леша
Писатель на заборах
Писатель на заборах
Сообщения: 150
Зарегистрирован: 20 июл 2004, 21:12

Re: Феи и ведьмы

Сообщение Леша »

Я умею это делать за 3/2k вопросов
UPD: Хотя нет, кажется я поторопился.

Ответить

Вернуться в «Задачки»