На главную страницу

Возврат к головоломкам

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

Ответ: Предлагаю два решения:
Решение 1: Сначала нам понадобится какое-нибудь утверждение, которое в настоящее время ни доказано, ни опровергнуто, истинность которого не известна европейцам. Например, подойдёт гипотеза "P=NP". Обозначим это высказывание буквой А. (Кто не помнит, P-класс задач, для решения которых существует полиномиальный алгоритм, NP-класс задач, для решения которых существует недетерминированный полиномиальный алгоритм.)
  Затем придумаем полезное для нас высказывание, истинность которого зависит от поведения туземца. Например, "Сейчас ты подпрыгнешь на левой ноге столько раз, сколько детей у вождя племени лжецов, на правой ноге - столько раз, сколько у него жён, и нарисуешь подробный план острова". Обозначим это высказывание буквой В. Высказывание В составлено из трёх высказываний, соединённых логическим И. Оно истинно тогда и только тогда, когда истинны ВСЕ три его части, то есть если туземец зачем-то всё это действительно проделает.
  Теперь можно задать вопрос: "Верно ли, что А или В?", где вместо А и В подставлены соответствующие высказывания.
  Утверждение "А или В", про истинность которого спрашивается, составлено из двух высказываний, соединённых логическим ИЛИ. Оно истинно тогда и только тогда, когда истинна ХОТЯ БЫ ОДНА его часть.
  Если высказывание В окажется истинным, то "А или В" будет истинным, независимо от значения А.
  Если высказывание В окажется ложным, то для выяснения истинности "А или В" будет необходимо выяснить истинность А, что для туземца затруднительно, потому что, по условию, он этого не знает (он знает логику и математику не лучше европейцев).
  Не отвечать или ответить "Не знаю" бедному бесправному туземцу тоже запрещено условиями задачи. Придётся туземцу обеспечить истинность В, то есть проделать всё то, о чём его просят.
  Таким образом, выслушав вопрос, правдивый туземец 18 раз подпрыгнет на левой ноге, 14 - на правой, нарисует подробный план острова и ответит "Да". Лжец проделает то же самое и ответит "Нет". (Попутно станет известно и племя туземца.)

Решение 2: Итак нам нужно узнать сколько детей у вождя.
- Если ты лжец, то подпрыгни НЕ столько раз, сколько детей у вождя лжецов; если же ты рыцарь, то подпрыгни столько раз, сколько детей у вождя лжецов :) После этого скажи, что бы ты ответил, если бы я спросил тебя лжец ли ты?
  Если туземец рыцарь, то он подпрыгнет 14 раз.
  А что если туземец лжец? Тогда, соблюдая все правила лжи (странно эта фраза звучит, на правда ли ;) он может выбрать любую стратегию поведения:
1) Он будет действовать, как рыцарь (сделав это он соврал нам)
2) Он неправильно исполнит действия лжеца, а значит подпрыгнет столько раз, сколько детей у вождя лжецов :)
  Последний вопрос нужен только потому, что в условиях говорится, что путешественник получил ответ "да" или "нет". Тем более, что мы, задав этот вопрос, узнали лжец ли туземец :)   Естественно вопрос можно расширить и узнать от скольких матерей были эти дети:
- Если ты лжец, то подпрыгни на левой ноге НЕ столько раз, сколько детей у вождя лжецов _ИЛИ_ на правой ноге не столько раз, от скольких жен эти дети; если же ты рыцарь, то подпрыгни на левой столько раз, сколько детей у вождя лжецов _И_ на правой ноге столько раз, сколько у него жен. После этого скажи, что бы ты ответил, если бы я спросил тебя лжец ли ты?
  Думаю здесь нужно немного пояснить:
  В случае "А или В" лжец обязан соврать и насчет А, и насчет В. Значит, если он будет действовать по стратегии 2, то он обязан соврать в обоих случаях, если по стратегии 1, то будет вести себя как рыцарь.
  Но нет ли здесь третьей стратегии - неправильное исполнение действий рыцаря (ведь этим он тоже нам солгет). То есть может он подпрыгнет на левой ноге столько раз, сколько детей у вождя, а на правой НЕ столько, от скольких жен эти дети. Но это невозможно, т.к. в этом случае он будет верно исполнять программу лжеца из нашего вопроса (т.к. истинное исполнение инструкции "А или В" означет верное исполнение хотя одной из её частей.)

PS: Не удивлюсь, если после этого туземец набьёт логику хитрую морду. :)