Задачи про честных и лгунов
Andrew Shabashev
из своей коллекции.
1. В некоторой стране есть два города. В одном из них живут только люди,
которые всегда говорят правду, в другом - только те, кто всегда лжет. Все
они ходят друг к другу в гости, т.е. в любом из этих двух городов можно
встретить как честного человека, так и лгуна. Предположим, вы оказались в
одном из этих городов. Как, задав один-единственный вопрос первому
встречному, определить, в какой город вы попали - в город честных или в
город лгунов?
2. Допустим, что вы - узник, которому вдруг предоставлено право выйти на
свободу, но только в том случае, если справитесь с таким заданием: перед
вами две двери, одна из них ведет на волю, другая - дорога к смерти. Сидят
два стражника, причем один из них - лгун, а второй всегда говорит правду; вы
не знаете, кто из них кто. Вы должны, задав лишь один вопрос одному из
стражников, определить дорогу на свободу. Какой вопрос вы зададите?
Удачи!
С уважением, Андрей Шабашев.
--------------------------------------------------------------------------
Подобные "серьезные" задачи, а также всякие хитрые загадки и задачи "с
подвохом" можно найти на моей странице - http://attend.to/andshab
Добро пожаловать!
Yuri Kaganov
9
8
7
6
5
4
3
2
1
0
>1. В некоторой стране есть два города. В одном из них живут только люди,
>которые всегда говорят правду, в другом - только те, кто всегда лжет. Все
>они ходят друг к другу в гости, т.е. в любом из этих двух городов можно
>встретить как честного человека, так и лгуна. Предположим, вы оказались в
>одном из этих городов. Как, задав один-единственный вопрос первому
>встречному, определить, в какой город вы попали - в город честных или в
>город лгунов?
"Вы местный ?"
>2. Допустим, что вы - узник, которому вдруг предоставлено право выйти на
>свободу, но только в том случае, если справитесь с таким заданием: перед
>вами две двери, одна из них ведет на волю, другая - дорога к смерти. Сидят
>два стражника, причем один из них - лгун, а второй всегда говорит правду;
вы
>не знаете, кто из них кто. Вы должны, задав лишь один вопрос одному из
>стражников, определить дорогу на свободу. Какой вопрос вы зададите?
"Как Ваш коллега ответит на вопрос, где дверь на волю ?"
Каганов
Andrew Shabashev
Привет!
Yuri Kaganov wrote in message ...
>>1. В некоторой стране есть два города. В одном из них живут только люди,
>>которые всегда говорят правду, в другом - только те, кто всегда лжет.
>>...
>"Вы местный ?"
Правильно! Другой вариант: "Вы находитесь в своем городе?"
>>2. Допустим, что вы - узник, которому вдруг предоставлено право выйти на
>>свободу, но только в том случае, если справитесь с таким заданием:
>>...
>"Как Ваш коллега ответит на вопрос, где дверь на волю ?"
А вот здесь не вполне корректно. Коллега-то всегда что-нибудь ответит, но
задача - с одного раза определить, где дорога на волю.
Андрей Шабашев.
Yuri Kaganov
>>>свободу, но только в том случае, если справитесь с таким заданием:
>>>...
>>"Как Ваш коллега ответит на вопрос, где дверь на волю ?"
>
>А вот здесь не вполне корректно. Коллега-то всегда что-нибудь ответит, но
>задача - с одного раза определить, где дорога на волю.
указал бы дверь на волю, но лжец инвертирует его ответ и покажет дверь на
смерть. Если же он спросил правдивого, то тот честно воспроизведет лживый
ответ своего коллеги и также покажет дверь на смерть. В любом случае надо
выходить в противоположную дверь.
Каганов
Dmitri Smirnov
Yuri Kaganov писал 06.10.98 16:23
В ответе не обязательно может звучать информация о том, где дверь на волю.
Может последовать такой ответ: "Он вам солжет". Если это скажет честный, то
он скажет правду, ведь его коллега всегда лжет. Если это скажет лгун, то
это и будет ложь, т.к. его коллега говорить неправду не может. Ни тот, ни
другой своим принципам в этой ситуации не изменит.
Думаю, что здесь должен быть прямой вопрос: да или нет. Годится такой
вопрос: "У двери на волю стоит лгун?". Рассмотрим варианты ответов:
1) Ответ "да". Если предположить, что это честный, то дверь на волю -
соседняя, т.к. себя честный лгуном не назовет, а лгуна-соседа - назовет.
Если же предположить, что это лгун, то опять-таки дверь на волю соседская,
потому что себя лгун лгуном не назовет, а честного соседа - запросто.
2) Ответ "нет". Если это честный, то дверь на волю - именно эта, если лгун
- тоже это, по аналогичным причинам. В обоих случаях все основывается на
том, что ни честный, ни лгун себя лгуном не назовет
Можно спросить и так "У двери к смерти стоит лгун". Тут рассуждения такие
же, как на предыдущий вопрос, но сочетание "на свободу" меняется на
сочетание "к смерти". Опять-таки, дверь на свободу определяется.
Yuri Kaganov (h)
>> указал бы дверь на волю, но лжец инвертирует его ответ и покажет дверь на
>> смерть. Если же он спросил правдивого, то тот честно воспроизведет лживый
>> ответ своего коллеги и также покажет дверь на смерть. В любом случае надо
>> выходить в противоположную дверь.
>
>В ответе не обязательно может звучать информация о том, где дверь на волю.
>Может последовать такой ответ: "Он вам солжет". Если это скажет честный, то
>он скажет правду, ведь его коллега всегда лжет. Если это скажет лгун, то
>это и будет ложь, т.к. его коллега говорить неправду не может. Ни тот, ни
>другой своим принципам в этой ситуации не изменит.
>Думаю, что здесь должен быть прямой вопрос: да или нет. Годится такой
>вопрос: "У двери на волю стоит лгун?".
более прямо: "Согласится ли Ваш коллега с тем, что левая дверь - на волю ?".
При ответе "Да" надо идти направо, "Нет" - налево. Этот вопрос несколько
лучше потому, что он не использует факт расположения охранников у каждой из
дверей. Может, они оба в центре комнаты ?
Каганов
Dmitri Smirnov
Yuri Kaganov писал 06.10.98 20:25
> >Думаю, что здесь должен быть прямой вопрос: да или нет. Годится такой
> >вопрос: "У двери на волю стоит лгун?".
> Да, этот вопрос решает задачу. Но и мой вопрос, если хотите, можно задать
> более прямо: "Согласится ли Ваш коллега с тем, что левая дверь - на волю
?".
> При ответе "Да" надо идти направо, "Нет" - налево. Этот вопрос несколько
> лучше потому, что он не использует факт расположения охранников у каждой
из
> дверей. Может, они оба в центре комнаты ?
Согласен. Я почему-то сразу решил, что стражники охраняют двери, сидя около
них, хотя в условии прямо об этом не говорится.
Yuri Kaganov (h)
А вот еще один красивый вариант решения:
"На какую дверь бы Вы указали человеку, который попросил бы Вас показать ему
дорогу на волю ?" - и смело идти в показанную дверь.
Каганов
Konstantin Knop
Честно говоря, я не ожидал, что две классических задачи о
лгунах и правдивых вызовут такое бурное обсуждение...
Попробую развить тему: вот еще одна задача того же рода,
но гораздо более сложная.
3. Узнику предоставлено право выйти на свободу, но только в
том случае, если он справится с третьим заданием: перед ним
две двери, одна из них ведет на волю, другая - дорога к
смерти. Здесь же сидят два стражника, причем один из них
либо "лжец", либо "правдец" а второй - "хитрец", то есть
человек, который говорит правду и ложь строго поочередно (то
есть либо на нечетные вопросы отвечает ложью, а на четные -
правдой, либо наоборот, на нечетные говорит правду, а на
четные - лжет). Оба стражника знают, какая из дорог ведет на
волю, но узнику неизвестно, кто из стражников хитрец. Узник
имеет право задать два вопроса одному из стражников. Как ему
определить дорогу, ведущую на свободу?
KK
Andrew Shabashev
Сначала - правильный ответ на задачу 2.
Yuri Kaganov wrote:
> ...... Но и мой вопрос, если хотите, можно задать
> более прямо: "Согласится ли Ваш коллега с тем, что левая дверь - на волю
?".
> При ответе "Да" надо идти направо, "Нет" - налево. Этот вопрос несколько
> лучше потому, что он не использует факт расположения охранников у каждой
из
> дверей. Может, они оба в центре комнаты ?
Абсолютно согласен! Это единственный вопрос, "инвариантный" к распололожению
охранников у дверей. А вот последняя версия -
- по-моему, равносильна следующей: "За какой дверью - дорога на волю?"
Никак не могу согласиться. Может, в этом варианте допущена опечатка?
Попробую ответить на третью задачу.
Konstantin Knop wrote in message ...
>3. Узнику предоставлено право выйти на свободу, но только в
>том случае, если он справится с третьим заданием: ...
>...
9
8
7
6
5
4
3
2
1
0
Вопрос 1: "На второй вопрос, который я тебе задам, ты скажешь правду?"
(ответ "да" будет означать, что перед нами либо стабильный "лжец", либо
стабильный "правдец". Ответ "нет" скажет о том, что перед нами "хитрец").
А теперь главное: второй вопрос зависит от ответа на первый. Как я понимаю,
никаких ограничений насчет того, являются ли оба вопроса заранее
предопределенными, не было.
Если на вопр.1 был получен ответ "нет":
Вопрос 2: (Показывая на любую дверь) "Отвечая мне в предыдущий раз, ты бы
сказал, что ЭТА дверь ведет на волю?"
(Ответ "нет" означает, что нужно идти в ту дверь, на которую показали, ответ
"да" - нужно идти в другую дверь.)
Если на вопр.1 был получен ответ "да":
Вопрос 2: (Показывая на любую дверь) "Если бы ты всегда говорил
противоположное (т.е. правду вместо лжи, или наоборот), ты бы сказал, что
ЭТА дверь ведет на волю?"
(Ответ "нет" означает, что нужно идти в ту дверь, на которую показали, ответ
"да" - нужно идти в другую дверь.)
К сожалению, не смог подобрать более красивого решения.
Андрей Шабашев.
Yuri Kaganov
>> "На какую дверь бы Вы указали человеку, который попросил бы Вас показать
>ему
>> дорогу на волю ?" - и смело идти в показанную дверь.
>
>- по-моему, равносильна следующей: "За какой дверью - дорога на волю?"
>Никак не могу согласиться. Может, в этом варианте допущена опечатка?
который попросил бы его показать дорогу на волю", он бы, естественно,
показал дорогу на смерть. Но он, будучи лжецом, не может в этом признаться и
показывает другую дверь, то есть на волю. Весь фокус в том, что этим
вопросом мы заставляем охранника дважды "пропустить через себя" информацию,
и "ориентация" охранника при этом уже не имеет значения. Вопрос хорош тем,
что он не использует факт наличия второго охранника.
>Попробую ответить на третью задачу.
Вот довольно простое решение.
1. Ты хитрец ?
2. Левая дверь на волю ?
Человек, ответивший на первый вопрос "да" - либо хитрец в правдивой фазе,
либо лжец. В любом случае твердо можно рассчитывать на то, что на второй
вопрос он солжет. Аналогичто человек, ответивший на первый вопрос "нет" -
либо хитрец в лживой фазе, либо правдец. В любом случае твердо можно
рассчитывать на то, что на второй вопрос он скажет правду.
Каганов