Задача про чёрное сердце (две в одной)
Добавлено: 19 мар 2016, 16:26
Рассказывают, что при дворе царя Хаммурапи было 1000 советников, которым он всецело доверял, и, благодаря их советам, весьма успешно правил . Вам известны, конечно, законы Хаммурапи, его военные и сельскохозяйственные победы., прочие заслуги. Именно с его правлением связано возвышение Вавилона. Впрочем, к задачке это не имеет никакого отношения.
Ближе к задаче. Хаммурапи доверял советникам не просто так – при зачислении на службу каждый из них принимал сыворотку правды, после чего врать Хаммурапи уже не мог. Но однажды служба собственной безопасности сообщила царю, что агенты вражеского государства Ларсы пытались завербовать некоторых советников. Завербованным советникам (назовём их «шпионами») ввели антисыворотку, и теперь они могут говорить и правду, и ложь царю, а сердце их почернело. Хаммурапи придумал, как избавиться от всех шпионов.
Собственно задача 1:
Хаммурапи собирает всех советников. Он не знает, кто из них шпион, но все советники друг про друга знают, кто остался верен царю, а кто завербован. Верный советник может говорить только правду царю, шпион может говорить и правду, и ложь. Хаммурапи задаёт каждому советнику по одному вопросу, на который можно ответить «да» или «нет», после чего одному из них вырывает сердце (если оно чёрное, значит, казнили шпиона – и только так можно отличить верного советника от завербованного). После этого следует следующий круг вопросов – каждому по одному, и вновь у одного из советников вырывают сердце – и так далее. В любой момент (например, уже после первого ответа первого круга вопросов) царь может остановить допрос и казни. Докажите, что при такой тактике Хаммурапи может казнить всех шпионов, казнив при этом не более одного верного советника.
Задача 2 (для любителей интернета): задачу не я придумала, но слегка изменила оригинальный текст, оставив при этом суть задачи так, что, как мне кажется, легче (и куда приятнее) решить, чем найти. Так что, если отыщете оригинальную версию – браво! Зачёт. Только в личку, пожалуйста, результаты поиска.
Ближе к задаче. Хаммурапи доверял советникам не просто так – при зачислении на службу каждый из них принимал сыворотку правды, после чего врать Хаммурапи уже не мог. Но однажды служба собственной безопасности сообщила царю, что агенты вражеского государства Ларсы пытались завербовать некоторых советников. Завербованным советникам (назовём их «шпионами») ввели антисыворотку, и теперь они могут говорить и правду, и ложь царю, а сердце их почернело. Хаммурапи придумал, как избавиться от всех шпионов.
Собственно задача 1:
Хаммурапи собирает всех советников. Он не знает, кто из них шпион, но все советники друг про друга знают, кто остался верен царю, а кто завербован. Верный советник может говорить только правду царю, шпион может говорить и правду, и ложь. Хаммурапи задаёт каждому советнику по одному вопросу, на который можно ответить «да» или «нет», после чего одному из них вырывает сердце (если оно чёрное, значит, казнили шпиона – и только так можно отличить верного советника от завербованного). После этого следует следующий круг вопросов – каждому по одному, и вновь у одного из советников вырывают сердце – и так далее. В любой момент (например, уже после первого ответа первого круга вопросов) царь может остановить допрос и казни. Докажите, что при такой тактике Хаммурапи может казнить всех шпионов, казнив при этом не более одного верного советника.
Задача 2 (для любителей интернета): задачу не я придумала, но слегка изменила оригинальный текст, оставив при этом суть задачи так, что, как мне кажется, легче (и куда приятнее) решить, чем найти. Так что, если отыщете оригинальную версию – браво! Зачёт. Только в личку, пожалуйста, результаты поиска.
