Рыцари и лжецы

[Мироника]

И как же быть?

[Таня Тайс]

VAL в сообщении #169435 писал(а):

Таня Тайс писал(а):

Мой вариант :
-Ты знаешь, сколько домов в деревне правдолюбов, или ты лжец?

Честный туземец, знающий сколько домов в его деревне, честно ответит "да". И как логик, услышав это "да", узнает сколько домов в деревне собеседника?

Тогда можно потребовать -"Докажи!"- а это уже не вопрос.

Лжец тоже ответит "да", потому что он не знает число домов в деревне правдолюбов, и т.о. высказывание становится правдивым, а это запрещено правилами.

И опять потребовав "докажи!", мы услышим число домов в деревне лжецов, т.к. назвав случайное число, он может случайно угадать, а это он понимает, и правду говорить не хочет.

[VAL]

Привожу решение задачи Олега Полубасова о числе домов в деревне туземца.

Ближе всех к решению подшел luitzen

luitzen в сообщении #168656 писал(а):

Может быть, нужно задать такой вопрос, чтобы у лжеца был единственный способ обеспечить ложность ответа на него: назвать число домов. И, соответственно, для туземца-правдолюба называние числа домов было бы единственным способом обеспечить истинность ответа.

Решение задачи основано на свойствах дизъюнкции. Как известно, она ложна лишь в том случае, когда ложны оба операнда.

Для наглядности отдельно укажу структуру вопроса, а затем уже сформулирую возможные его составляющие.

Вопрос, решающий задачу, может иметь вид: верно ли утверждение $a \vee b$?
Высказывание $a$ должно быть таким, чтобы туземец не знал, истинно ли оно, и не имел возможности проверить его истинность.
Автор задачи, Олег Полубасов, предлагал в качестве $a$ использовать какую-нибудь не доказанную, но и не опровергную математическую гипотезу. Именно поэтому он включил в условие информацию об обширных познаниях туземца.

Мне представляется, что можно взять в качестве $a$ что-нибудь попроще. Например, "К началу 22-го столетия население Франции превысит 100 000 000 человек". Понятно, что на сегодняшний день никто не может гарантированно ответить истинно ли приведеное утверждение. Трудно даже сказать будет ли к этому времени существовть сама Франция (неважно, в рамках Евросоюза или еще как-то). А ждать долго. Велика вероятность не дождаться

Утверждение $b$ может выглядеть примерно так: "Сейчас ты разборчиво напишешь на этом листке единственное число (в десятичной системе счисления), совпадающее с числом домов в твоей деревне, и при этом никоим образом не будешь препятствовать тому, чтобы я прочел и нонял написанное."

Если дополнительных условий, которыми я, на всякий случай, снабдил $b$ недостаточно, добавьте еще.

Итак вопрос прозвучал. Что делать бедному туземцу? Если он не напишет нужное число, истинность дизъюнкции будет зависеть от истинности $a$, а определить ее не представляется возможным. Зато если он напишет требуемое число, вся дизъюнкция станет истинной. Поэтому туземец напишет нужное число. И только после этого честный облегченно произнесет "Да", а лжец радостно скажет "Нет".

Понятно, что приведенный способ позволяет выведать у туземца любые доступные ему сведения (например, кто Маша, а кто Даша). Единственным недостатком метода является его низкая эффективность при общении не с задачными туземцами, а с реальными людьми

[TOTAL]

VAL писал(а):

Единственным недостатком метода является его низкая эффективность при общении не с задачными туземцами, а с реальными людьми

Несомненным достоинством метода является также то, что он не удовлетворяет условиям
(превращая "задачу", как было понятно сразу, в обыкновенный лохотрон):

Цитата:

5. Туземец отвечает только "Да" или "Hет".
6. Путешественник задаёт только те вопросы, на которые туземец может
ответить.

[AGu]

TOTAL писал(а):

Несомненным достоинством метода является также то, что он не удовлетворяет условиям
(превращая "задачу", как было понятно сразу, в обыкновенный лохотрон):

Цитата:

5. Туземец отвечает только "Да" или "Hет".
6. Путешественник задаёт только те вопросы, на которые туземец может
ответить.

Откровенно говоря, я тоже попался в эту ловушку. Я даже знал аналогичные головоломки, идея решения которых основана на неразрешимых/сложных дизъюнктах, но подумал, что условие 6 заведомо устраняет этот подход. Оказывается, нет: ведь туземец и впрямь может ответить на поставленный вопрос (если обеспечит истинность второго дизъюнкта), а значит у путешественника есть шанс получить ответ.

Веселая задачка, спасибо.

[TOTAL]

AGu писал(а):

ведь туземец и впрямь может ответить на поставленный вопрос (если обеспечит истинность второго дизъюнкта), а значит у путешественника есть шанс получить ответ.

Не согласен. Туземец может отвечать только "да" или "нет". Условие запрещает использовать рисование и т.д.

[AGu]

TOTAL писал(а):

Туземец может отвечать только "да" или "нет". Условие запрещает использовать рисование и т.д.

Так он и отвечает только "да" или "нет". Рисование -- это не часть ответа, это часть "вычисления истинности".

[TOTAL]

AGu писал(а):

TOTAL писал(а):

Туземец может отвечать только "да" или "нет". Условие запрещает использовать рисование и т.д.

Так он и отвечает только "да" или "нет". Рисование -- это не часть ответа, это часть "вычисления истинности".

Ответ - это то, что получает путешественник в ответ на свой вопрос.
То есть путешественник должен услышать (увидеть) только "да" или "нет".

[luitzen]

TOTAL писал(а):

То есть путешественник должен услышать (увидеть) только "да" или "нет".

А ещё надо запретить писать вещи наподобие

while(--i>0){…}

и прочие “side effects”

Мне, если честно, это всё тоже не нравится. Надо будет глянуть, нельзя ли в условиях этой задачи схлопотать какой-нибудь парадокс: рассуждения о будущих случайных событиях в терминах классической пропозициональной логики мне кажутся рискованными.

Хотя, наверное, и без будущих случайных событий можно что-нибудь отыскать: человек, который всегда лжёт, фигура такая… сомнительная.

[Таня Тайс]

luitzen в сообщении #169910 писал(а):

Хотя, наверное, и без будущих случайных событий можно что-нибудь отыскать: человек, который всегда лжёт, фигура такая… сомнительная.

А человек, который всегда говорит правду, такая примитивная, знаете ли, фигура.

[luitzen]

Таня Тайс писал(а):

luitzen в сообщении #169910 писал(а):

Хотя, наверное, и без будущих случайных событий можно что-нибудь отыскать: человек, который всегда лжёт, фигура такая… сомнительная.

А человек, который всегда говорит правду, такая примитивная, знаете ли, фигура.

Ну, в том смысле сомнительная, что её существование сомнительно из чисто логических соображений .

[Таня Тайс]

VAL в сообщении #169709 писал(а):

Утверждение может выглядеть примерно так: "Сейчас ты разборчиво напишешь на этом листке единственное число (в десятичной системе счисления), совпадающее с числом домов в твоей деревне, и при этом никоим образом не будешь препятствовать тому, чтобы я прочел и нонял написанное."

VAL в сообщении #169709 писал(а):

Итак вопрос прозвучал.

Вопросом назывется всё, что имеет в конце знак вопроса

[TOTAL]

AGu писал(а):

TOTAL писал(а):

Туземец может отвечать только "да" или "нет". Условие запрещает использовать рисование и т.д.

Так он и отвечает только "да" или "нет". Рисование -- это не часть ответа, это часть "вычисления истинности".

Застрелил инкассатора, забрал деньги, закурил. Чисто конкретно логически был оправдан. Так как убийство являлось не частью грабежа, а частью процесса курения, которое не запрещено.

[AGu]

TOTAL писал(а):

То есть путешественник должен услышать (увидеть) только "да" или "нет".

Я все же склонен считать это требование произвольным усилением условия задачи.
Ну а если его принять, то, наверное, единственной лазейкой останется финт с "заиканием" (см. выше), т.е. "да" у туземцев такое своеобразное, многозвучное.

Кстати, финт с заиканием можно оформить строго логически. В условии нигде не сказано, какой именно логикой пользуются туземцы. Она вполне может оказаться булевозначной, где булевой алгеброй значений истинности является множество $\mathcal P(H)$ всех подмножеств множества $H=H_t\cup H_f$ всех "правдивых" и "лживых" домов, а ответ на вопрос об истинности утверждения $\varphi$ является множеством $\{h\in H : h\vDash\varphi\}$, где $h\vDash\varphi$ -- двузначная истинность утверждения $\varphi$, вычисленная внутри дома $h$. Тогда можно задать такой вопрос: "Верно ли, что ты находишься в доме правдивой деревни?". Ответом правдивого туземца будет $H_t$, а ответом лжеца -- $H_f$. При этом искомое число легко получить, вычислив мощность ответа.

[TOTAL]

У меня тоже есть решение, нарушающее условие.
Вопрос: "Верно ли хотя бы одно из двух: либо число дней с начала нашего знакомства равно числу домов, либо твой ответ совпадает с твоим ответом на вопрос "верно ли что 2=1?"?"