Задача про чёрное сердце (две в одной)

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

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

Ответить
Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

Задача про чёрное сердце (две в одной)

Сообщение Тоня »

Рассказывают, что при дворе царя Хаммурапи было 1000 советников, которым он всецело доверял, и, благодаря их советам, весьма успешно правил . Вам известны, конечно, законы Хаммурапи, его военные и сельскохозяйственные победы., прочие заслуги. Именно с его правлением связано возвышение Вавилона. Впрочем, к задачке это не имеет никакого отношения.

Ближе к задаче. Хаммурапи доверял советникам не просто так – при зачислении на службу каждый из них принимал сыворотку правды, после чего врать Хаммурапи уже не мог. Но однажды служба собственной безопасности сообщила царю, что агенты вражеского государства Ларсы пытались завербовать некоторых советников. Завербованным советникам (назовём их «шпионами») ввели антисыворотку, и теперь они могут говорить и правду, и ложь царю, а сердце их почернело. Хаммурапи придумал, как избавиться от всех шпионов.

Собственно задача 1:
Хаммурапи собирает всех советников. Он не знает, кто из них шпион, но все советники друг про друга знают, кто остался верен царю, а кто завербован. Верный советник может говорить только правду царю, шпион может говорить и правду, и ложь. Хаммурапи задаёт каждому советнику по одному вопросу, на который можно ответить «да» или «нет», после чего одному из них вырывает сердце (если оно чёрное, значит, казнили шпиона – и только так можно отличить верного советника от завербованного). После этого следует следующий круг вопросов – каждому по одному, и вновь у одного из советников вырывают сердце – и так далее. В любой момент (например, уже после первого ответа первого круга вопросов) царь может остановить допрос и казни. Докажите, что при такой тактике Хаммурапи может казнить всех шпионов, казнив при этом не более одного верного советника.

Задача 2 (для любителей интернета): задачу не я придумала, но слегка изменила оригинальный текст, оставив при этом суть задачи так, что, как мне кажется, легче (и куда приятнее) решить, чем найти. Так что, если отыщете оригинальную версию – браво! Зачёт. Только в личку, пожалуйста, результаты поиска.

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

Re: Задача про чёрное сердце (две в одной)

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

Вроде получается.

(В прозрачном виде.)
1. Берем из числа советников Васю, ставим его перед строем остальных и начинаем задавать им вопрос: "Вася - шпион?".

2. Первого, ответившего "Нет", - казним.
2а. Если он шпион, возвращаемся к пункту 1.
2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут).

3. Если все ответили "Да" - казним Васю.
3а. Если Вася шпион - выбираем "нового Васю" и возвращаемся к пункту 1.
3б. Если Вася честный - значит, все врут и все они шпионы. Казним всех остальных (Погиб единственный честный Вася, все остальные оказались шпионами).

4. Строим всех в затылок, честный Вася встает последним. Спрашиваем, начиная с Васи: "Перед тобой честный советник?". Ответ "Да" снимает подозрения, ответ "Нет" идентифицирует шпиона. Казним его и возвращаемся к пункту 4 сначала (для ускорения дела можно сразу освобождать оправданных советников - кроме Васи, естественно.)

Все!
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

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

Re: Задача про чёрное сердце (две в одной)

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

А нет не все.

Возможен еще вариант, когда все советники проявились как шпионы по пункту 2а и остался один Вася. Его придется в этом случае тоже придется прикончить, для гарантии.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

Re: Задача про чёрное сердце (две в одной)

Сообщение Шшок »

Юляша писал(а):Вроде получается.
А у меня совершенно противоположная идея. Я буду всем задавать вопрос "Вася - честный?", и выдеру сердце первому, кто ответит "да". Остальное - по алгоритму Юляши.
В борьбе бобра с козлом побеждает бобро. Или козло.

Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

Re: Задача про чёрное сердце (две в одной)

Сообщение Тоня »

Юляша, Шшок, как ни поразительно, при абсолютно зеркально противоположных подходах у вас у обоих получился абсолютно правильный ответ! :)

Аватара пользователя
maksim82
Популярный автор
Популярный автор
Сообщения: 1813
Зарегистрирован: 28 июн 2005, 17:28
Пол: Мужской
Откуда: Москва

Re: Задача про чёрное сердце (две в одной)

Сообщение maksim82 »

Юляша писал(а): 2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут)
Все!
Вообще не значит. Как я понял, шпионы могут и правду говорить, и врать. Таким образом, однозначно выявить, шпион перед нами или нет, можно только вырезав сердце.
У меня в голове опилки. Длинные слова меня только расстраивают

Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

Re: Задача про чёрное сердце (две в одной)

Сообщение Шшок »

maksim82 писал(а):
Юляша писал(а): 2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут)
Все!
Вообще не значит. Как я понял, шпионы могут и правду говорить, и врать. Таким образом, однозначно выявить, шпион перед нами или нет, можно только вырезав сердце.
А мы у шпионов ничего и не спрашиваем. Мы сначала спрашиваем Васю (мы уже выяснили, что он честный). Если перед Васей стоит шпион, мы этого шпиона тут же казним. А после казни, по условиям задачи, снова можно задавать вопрос Васе.
Если же Вася утверждает, что перед ним стоит честный, то мы верим Васе и задаем следующий вопрос тому, кто стоит перед Васей (он честный по заверениям Васи). И так далее.
В борьбе бобра с козлом побеждает бобро. Или козло.

Аватара пользователя
maksim82
Популярный автор
Популярный автор
Сообщения: 1813
Зарегистрирован: 28 июн 2005, 17:28
Пол: Мужской
Откуда: Москва

Re: Задача про чёрное сердце (две в одной)

Сообщение maksim82 »

Спасибо, разобрался))
У меня в голове опилки. Длинные слова меня только расстраивают

Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

Re: Задача про чёрное сердце (две в одной)

Сообщение Тоня »

Шшок, спасибо, что помог Максиму разобраться.
Вопрос к игрокам - логических задач в инете сейчас море вместе с ответами. У меня есть несколько (тоже попавших, конечно, в базы) задач, которые сама прорешала, которые показались интересными - дочка с олимпиад притаскивает регулярно кучами. Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?

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

Re: Задача про чёрное сердце (две в одной)

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

Конечно постить интересные задачи!

(Кстати, первоисточник задачи про черное сердце тоже интересен - она была мне незнакома.)
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Тоня
Популярный автор
Популярный автор
Сообщения: 2526
Зарегистрирован: 29 июн 2005, 21:45
Пол: Женский

Re: Задача про чёрное сердце (две в одной)

Сообщение Тоня »

Пошуршу, запостю, спасибо.
Оригинальная задача с ответом здесь:
http://ashap.info/Turniry/TG/36v.pdf
8-9 классы, сложный вариант, задача 7

Аватара пользователя
maksim82
Популярный автор
Популярный автор
Сообщения: 1813
Зарегистрирован: 28 июн 2005, 17:28
Пол: Мужской
Откуда: Москва

Re: Задача про чёрное сердце (две в одной)

Сообщение maksim82 »

Тоня писал(а):Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?
Конечно!
У меня в голове опилки. Длинные слова меня только расстраивают

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задача про чёрное сердце (две в одной)

Сообщение Dendr »

Надо-надо!

Конечно, ищущий да обрящет, но в сети находятся чаще всего вопросы с федеральных состязаний. А вот с региональных реже, но и там есть перлы.

Ответить

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