Задача про чёрное сердце (две в одной)
Модераторы: Азарапетыч, Администрация
Задача про чёрное сердце (две в одной)
Рассказывают, что при дворе царя Хаммурапи было 1000 советников, которым он всецело доверял, и, благодаря их советам, весьма успешно правил . Вам известны, конечно, законы Хаммурапи, его военные и сельскохозяйственные победы., прочие заслуги. Именно с его правлением связано возвышение Вавилона. Впрочем, к задачке это не имеет никакого отношения.
Ближе к задаче. Хаммурапи доверял советникам не просто так – при зачислении на службу каждый из них принимал сыворотку правды, после чего врать Хаммурапи уже не мог. Но однажды служба собственной безопасности сообщила царю, что агенты вражеского государства Ларсы пытались завербовать некоторых советников. Завербованным советникам (назовём их «шпионами») ввели антисыворотку, и теперь они могут говорить и правду, и ложь царю, а сердце их почернело. Хаммурапи придумал, как избавиться от всех шпионов.
Собственно задача 1:
Хаммурапи собирает всех советников. Он не знает, кто из них шпион, но все советники друг про друга знают, кто остался верен царю, а кто завербован. Верный советник может говорить только правду царю, шпион может говорить и правду, и ложь. Хаммурапи задаёт каждому советнику по одному вопросу, на который можно ответить «да» или «нет», после чего одному из них вырывает сердце (если оно чёрное, значит, казнили шпиона – и только так можно отличить верного советника от завербованного). После этого следует следующий круг вопросов – каждому по одному, и вновь у одного из советников вырывают сердце – и так далее. В любой момент (например, уже после первого ответа первого круга вопросов) царь может остановить допрос и казни. Докажите, что при такой тактике Хаммурапи может казнить всех шпионов, казнив при этом не более одного верного советника.
Задача 2 (для любителей интернета): задачу не я придумала, но слегка изменила оригинальный текст, оставив при этом суть задачи так, что, как мне кажется, легче (и куда приятнее) решить, чем найти. Так что, если отыщете оригинальную версию – браво! Зачёт. Только в личку, пожалуйста, результаты поиска.
Ближе к задаче. Хаммурапи доверял советникам не просто так – при зачислении на службу каждый из них принимал сыворотку правды, после чего врать Хаммурапи уже не мог. Но однажды служба собственной безопасности сообщила царю, что агенты вражеского государства Ларсы пытались завербовать некоторых советников. Завербованным советникам (назовём их «шпионами») ввели антисыворотку, и теперь они могут говорить и правду, и ложь царю, а сердце их почернело. Хаммурапи придумал, как избавиться от всех шпионов.
Собственно задача 1:
Хаммурапи собирает всех советников. Он не знает, кто из них шпион, но все советники друг про друга знают, кто остался верен царю, а кто завербован. Верный советник может говорить только правду царю, шпион может говорить и правду, и ложь. Хаммурапи задаёт каждому советнику по одному вопросу, на который можно ответить «да» или «нет», после чего одному из них вырывает сердце (если оно чёрное, значит, казнили шпиона – и только так можно отличить верного советника от завербованного). После этого следует следующий круг вопросов – каждому по одному, и вновь у одного из советников вырывают сердце – и так далее. В любой момент (например, уже после первого ответа первого круга вопросов) царь может остановить допрос и казни. Докажите, что при такой тактике Хаммурапи может казнить всех шпионов, казнив при этом не более одного верного советника.
Задача 2 (для любителей интернета): задачу не я придумала, но слегка изменила оригинальный текст, оставив при этом суть задачи так, что, как мне кажется, легче (и куда приятнее) решить, чем найти. Так что, если отыщете оригинальную версию – браво! Зачёт. Только в личку, пожалуйста, результаты поиска.
Re: Задача про чёрное сердце (две в одной)
Вроде получается.
(В прозрачном виде.)
1. Берем из числа советников Васю, ставим его перед строем остальных и начинаем задавать им вопрос: "Вася - шпион?".
2. Первого, ответившего "Нет", - казним.
2а. Если он шпион, возвращаемся к пункту 1.
2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут).
3. Если все ответили "Да" - казним Васю.
3а. Если Вася шпион - выбираем "нового Васю" и возвращаемся к пункту 1.
3б. Если Вася честный - значит, все врут и все они шпионы. Казним всех остальных (Погиб единственный честный Вася, все остальные оказались шпионами).
4. Строим всех в затылок, честный Вася встает последним. Спрашиваем, начиная с Васи: "Перед тобой честный советник?". Ответ "Да" снимает подозрения, ответ "Нет" идентифицирует шпиона. Казним его и возвращаемся к пункту 4 сначала (для ускорения дела можно сразу освобождать оправданных советников - кроме Васи, естественно.)
Все!
(В прозрачном виде.)
1. Берем из числа советников Васю, ставим его перед строем остальных и начинаем задавать им вопрос: "Вася - шпион?".
2. Первого, ответившего "Нет", - казним.
2а. Если он шпион, возвращаемся к пункту 1.
2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут).
3. Если все ответили "Да" - казним Васю.
3а. Если Вася шпион - выбираем "нового Васю" и возвращаемся к пункту 1.
3б. Если Вася честный - значит, все врут и все они шпионы. Казним всех остальных (Погиб единственный честный Вася, все остальные оказались шпионами).
4. Строим всех в затылок, честный Вася встает последним. Спрашиваем, начиная с Васи: "Перед тобой честный советник?". Ответ "Да" снимает подозрения, ответ "Нет" идентифицирует шпиона. Казним его и возвращаемся к пункту 4 сначала (для ускорения дела можно сразу освобождать оправданных советников - кроме Васи, естественно.)
Все!
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Задача про чёрное сердце (две в одной)
А нет не все.
Возможен еще вариант, когда все советники проявились как шпионы по пункту 2а и остался один Вася. Его придется в этом случае тоже придется прикончить, для гарантии.
Возможен еще вариант, когда все советники проявились как шпионы по пункту 2а и остался один Вася. Его придется в этом случае тоже придется прикончить, для гарантии.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
- Шшок
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: Задача про чёрное сердце (две в одной)
А у меня совершенно противоположная идея. Я буду всем задавать вопрос "Вася - честный?", и выдеру сердце первому, кто ответит "да". Остальное - по алгоритму Юляши.Юляша писал(а):Вроде получается.
В борьбе бобра с козлом побеждает бобро. Или козло.
Re: Задача про чёрное сердце (две в одной)
Юляша, Шшок, как ни поразительно, при абсолютно зеркально противоположных подходах у вас у обоих получился абсолютно правильный ответ!
- maksim82
- Популярный автор
- Сообщения: 1813
- Зарегистрирован: 28 июн 2005, 17:28
- Пол: Мужской
- Откуда: Москва
Re: Задача про чёрное сердце (две в одной)
Вообще не значит. Как я понял, шпионы могут и правду говорить, и врать. Таким образом, однозначно выявить, шпион перед нами или нет, можно только вырезав сердце.Юляша писал(а): 2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут)
Все!
У меня в голове опилки. Длинные слова меня только расстраивают
- Шшок
- Акула пера
- Сообщения: 9096
- Зарегистрирован: 28 ноя 2003, 14:05
- Пол: Мужской
- Откуда: С большой дороги.
Re: Задача про чёрное сердце (две в одной)
А мы у шпионов ничего и не спрашиваем. Мы сначала спрашиваем Васю (мы уже выяснили, что он честный). Если перед Васей стоит шпион, мы этого шпиона тут же казним. А после казни, по условиям задачи, снова можно задавать вопрос Васе.maksim82 писал(а):Вообще не значит. Как я понял, шпионы могут и правду говорить, и врать. Таким образом, однозначно выявить, шпион перед нами или нет, можно только вырезав сердце.Юляша писал(а): 2б. Если он честный, то значит и Вася честный, переходим к пункту 4 (больше честные советники не погибнут)
Все!
Если же Вася утверждает, что перед ним стоит честный, то мы верим Васе и задаем следующий вопрос тому, кто стоит перед Васей (он честный по заверениям Васи). И так далее.
В борьбе бобра с козлом побеждает бобро. Или козло.
- maksim82
- Популярный автор
- Сообщения: 1813
- Зарегистрирован: 28 июн 2005, 17:28
- Пол: Мужской
- Откуда: Москва
Re: Задача про чёрное сердце (две в одной)
Спасибо, разобрался))
У меня в голове опилки. Длинные слова меня только расстраивают
Re: Задача про чёрное сердце (две в одной)
Шшок, спасибо, что помог Максиму разобраться.
Вопрос к игрокам - логических задач в инете сейчас море вместе с ответами. У меня есть несколько (тоже попавших, конечно, в базы) задач, которые сама прорешала, которые показались интересными - дочка с олимпиад притаскивает регулярно кучами. Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?
Вопрос к игрокам - логических задач в инете сейчас море вместе с ответами. У меня есть несколько (тоже попавших, конечно, в базы) задач, которые сама прорешала, которые показались интересными - дочка с олимпиад притаскивает регулярно кучами. Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?
Re: Задача про чёрное сердце (две в одной)
Конечно постить интересные задачи!
(Кстати, первоисточник задачи про черное сердце тоже интересен - она была мне незнакома.)
(Кстати, первоисточник задачи про черное сердце тоже интересен - она была мне незнакома.)
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Задача про чёрное сердце (две в одной)
Пошуршу, запостю, спасибо.
Оригинальная задача с ответом здесь:
http://ashap.info/Turniry/TG/36v.pdf
8-9 классы, сложный вариант, задача 7
Оригинальная задача с ответом здесь:
http://ashap.info/Turniry/TG/36v.pdf
8-9 классы, сложный вариант, задача 7
- maksim82
- Популярный автор
- Сообщения: 1813
- Зарегистрирован: 28 июн 2005, 17:28
- Пол: Мужской
- Откуда: Москва
Re: Задача про чёрное сердце (две в одной)
Конечно!Тоня писал(а):Есть ли смысл постить или и без того, кому интересно, найдёт чем себя озадачить?
У меня в голове опилки. Длинные слова меня только расстраивают
- Dendr
- Акула пера
- Сообщения: 5717
- Зарегистрирован: 06 май 2005, 15:11
- Пол: Мужской
- Откуда: Раменское, Мос.обл.
- Контактная информация:
Re: Задача про чёрное сердце (две в одной)
Надо-надо!
Конечно, ищущий да обрящет, но в сети находятся чаще всего вопросы с федеральных состязаний. А вот с региональных реже, но и там есть перлы.
Конечно, ищущий да обрящет, но в сети находятся чаще всего вопросы с федеральных состязаний. А вот с региональных реже, но и там есть перлы.