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

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

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

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

Сообщение Тоня » 19 мар 2016, 16:26

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

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

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

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

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

Сообщение Юляша » 20 мар 2016, 12:31

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

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

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

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

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

Все!
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3158
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Юляша » 20 мар 2016, 12:41

А нет не все.

Возможен еще вариант, когда все советники проявились как шпионы по пункту 2а и остался один Вася. Его придется в этом случае тоже придется прикончить, для гарантии.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3158
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Шшок » 21 мар 2016, 14:12

Юляша писал(а):Вроде получается.



А у меня совершенно противоположная идея. Я буду всем задавать вопрос "Вася - честный?", и выдеру сердце первому, кто ответит "да". Остальное - по алгоритму Юляши.
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

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

Сообщение Тоня » 21 мар 2016, 16:29

Юляша, Шшок, как ни поразительно, при абсолютно зеркально противоположных подходах у вас у обоих получился абсолютно правильный ответ! :)
Тоня
Популярный автор
Популярный автор
 
Сообщения: 1597
Зарегистрирован: 29 июн 2005, 21:45

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

Сообщение maksim82 » 28 мар 2016, 11:34

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

Вообще не значит. Как я понял, шпионы могут и правду говорить, и врать. Таким образом, однозначно выявить, шпион перед нами или нет, можно только вырезав сердце.
У меня в голове опилки. Длинные слова меня только расстраивают
Аватара пользователя
maksim82
Популярный автор
Популярный автор
 
Сообщения: 1812
Зарегистрирован: 28 июн 2005, 17:28
Откуда: Москва

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

Сообщение Шшок » 28 мар 2016, 14:35

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

Вообще не значит. Как я понял, шпионы могут и правду говорить, и врать. Таким образом, однозначно выявить, шпион перед нами или нет, можно только вырезав сердце.


А мы у шпионов ничего и не спрашиваем. Мы сначала спрашиваем Васю (мы уже выяснили, что он честный). Если перед Васей стоит шпион, мы этого шпиона тут же казним. А после казни, по условиям задачи, снова можно задавать вопрос Васе.
Если же Вася утверждает, что перед ним стоит честный, то мы верим Васе и задаем следующий вопрос тому, кто стоит перед Васей (он честный по заверениям Васи). И так далее.
В борьбе бобра с козлом побеждает бобро. Или козло.
Аватара пользователя
Шшок
Акула пера
Акула пера
 
Сообщения: 8575
Зарегистрирован: 28 ноя 2003, 14:05
Откуда: С большой дороги.

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

Сообщение maksim82 » 28 мар 2016, 14:58

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

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

Сообщение Тоня » 28 мар 2016, 19:04

Шшок, спасибо, что помог Максиму разобраться.
Вопрос к игрокам - логических задач в инете сейчас море вместе с ответами. У меня есть несколько (тоже попавших, конечно, в базы) задач, которые сама прорешала, которые показались интересными - дочка с олимпиад притаскивает регулярно кучами. Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?
Тоня
Популярный автор
Популярный автор
 
Сообщения: 1597
Зарегистрирован: 29 июн 2005, 21:45

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

Сообщение Юляша » 28 мар 2016, 21:31

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

(Кстати, первоисточник задачи про черное сердце тоже интересен - она была мне незнакома.)
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3158
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Тоня » 28 мар 2016, 22:59

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

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

Сообщение maksim82 » 29 мар 2016, 13:41

Тоня писал(а):Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?
Конечно!
У меня в голове опилки. Длинные слова меня только расстраивают
Аватара пользователя
maksim82
Популярный автор
Популярный автор
 
Сообщения: 1812
Зарегистрирован: 28 июн 2005, 17:28
Откуда: Москва

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

Сообщение Dendr » 29 мар 2016, 14:26

Надо-надо!

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


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

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1