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

[TOTAL]

Brukvalub писал(а):

TOTAL= Архипов???

Вот-вот! Здесь так много данных, но отличить TOTAL от Архипов все равно трудно!
Как же нам отличить Машу от Даши всего по одному вопросу?

[VAL]

TOTAL писал(а):

VAL писал(а):

Вопрос, должен быть без обращения. Поэтому решения типа "одна ответит, а другая промолчит" не годятся.

Непонятное требование.
Непонятно также, знают ли сёстры о существовании друг друга и о правдивости друг друга.
Знает ли каждая из них, что вопрос задают также и сестре.
Знает ли сестра, что она первая (вторая) отвечает на вопрос и слышит ли предыдущий ответ.
Знает ли, что вопрос один и тот же.

Все ответы "да". Хотя знание о правдивости друг друга не обязательно. Зато они знают, как кого зовут.

Цитата:

То есть можно ли сформулировать задачу так. В разных городах, не зная о существовании друг друга, живут сестры. Им задают один и тот же вопрос. Определить имя и правдивость каждой.

Можно. Но это будет совсем другая задача. А приведенная мной начинается со слов "Перед Вами..."

[TOTAL]

Девочка, либо ты отвечаешь первой, либо ты Маша. Да?

[Nxx]

Есть ли среди вас Маша? Та, которая ответит "нет" - лгунья.

Ну или вас двое?

[Brukvalub]

TOTAL в сообщении #168357 писал(а):

Девочка, либо ты отвечаешь первой, либо ты Маша. Да?

Напомнило одно из списка "крылатых" армейских высказываний: "Эй, слушайте сюда, это я вам говорю, или где!"
Также неплохо подходит альтернатива из к./ф. "Кавказская пленница:"Теперь либо я веду ее в ЗАГС, либо она ведет меня к прокурору"

[TOTAL]

Nxx писал(а):

Ну или вас двое?

Она ответит да. Как её зовут?

Добавлено спустя 2 минуты 52 секунды:

TOTAL писал(а):

Девочка, либо ты отвечаешь первой, либо ты Маша. Да?

Здесь объединяющее ИЛИ. Ответ первой девочки укажет лгунью. Ответ второй девочки укажет Машу.

[VAL]

TOTAL писал(а):

Девочка, либо ты отвечаешь первой, либо ты Маша. Да?

Угу.
Мой вариант был: "Маша уже ответила на мой вопрос до тебя?"

Добавлено спустя 3 минуты 29 секунд:

Nxx писал(а):

Есть ли среди вас Маша? Та, которая ответит "нет" - лгунья.
Ну или вас двое?

Оба варианта не позволят узнать, кто Маша, кто Даша.
А вот вопрос Total'a позволит.

[VAL]

С Машей и Дашей разобрались.
А теперь обещанная удивительная задачка.

Цитата:

Логик оказался на острове, который, как водится в задачах этого
рода, населяли племя лжецов и племя правдивых туземцев. Члены первого
племени всегда лгали, члены второго всегда говорили только правду.
Путешественник встретил туземца, неизвестно, правдивого или нет.
Как, задав единственный вопрос и получив в ответ "Да" или "Hет",
путешественник узнал, сколько домов в деревне туземца?
Считаем, что туземцы знают логику и математику ровно в таком же объеме,
что и европейцы.

Hаученный опытом предыдущего треда, даю подсказки.
1. Туземец знает, сколько домов в его деревне.
2. Путешественник знает, что туземец знает, сколько домов в его деревне.
3. Путешественник заранее не знает, сколько домов в деревне туземца.
4. Путешественник не угадал случайно, сколько домов в деревне туземца.
5. Туземец отвечает только "Да" или "Hет".
6. Путешественник задаёт только те вопросы, на которые туземец может
ответить.
7. Это не данетка.
8. Это не загадка.
9. Это не шутка. Игры слов нет. Просто трудная логическая задача.
10. Для её решения кроме логики неплохо бы знать и кое-какие другие
разделы математики.
11. Путешественник знает логику и математику ровно в таком же объеме,
что и европейцы.
12. Объем знаний европейцев состоит из всех знаний современной науки.
13. Каждый житель сначала вычисляет истинность высказывания, а затем
честный сообщает правильное значение, а лжец - инвертированное.
Лжец не инвертирует значения аргументов и промежуточных выражений
(то есть не лжёт самому себе), лжёт только при ответе.

Олег Полубасов. (с)

От себя добавлю, что знать другие разделы математики, конечно, неплохо, но для решения данной задачи совсем не обязательно.

[Alexiii]

antbez писал(а):

Цитата:

Предложение ложно только при истинности .
Из сего следует,что лжец не мог сказать эти слова,то есть говорил рыцарь.

Неверно! Лжец всегда лжёт, почему бы ему не выдать себя за рыцаря?

Не согласен!
Лжец говорит ложно всё предложение: коли я рыцарь,то он лжец.А то,что

Цитата:

Предложение ложно только при истинности .

,это уже не задачка решает,а предмет логики.

[nikov]

VAL писал(а):

Цитата:

Как, задав единственный вопрос и получив в ответ "Да" или "Hет",
путешественник узнал, сколько домов в деревне туземца?

Не нужно умалчивать, что логик получает еще любое количество визуальной информации о поведении туземца.

[VAL]

nikov писал(а):

VAL писал(а):

Цитата:

Как, задав единственный вопрос и получив в ответ "Да" или "Hет",
путешественник узнал, сколько домов в деревне туземца?

Не нужно умалчивать, что логик получает еще любое количество визуальной информации о поведении туземца.

А в каком именно месте условия об этом умалчивается?

И вообще! Задачка не моя. Я без искажений привел авторское условие и более поздние комментарии Олега.

[ddn]

VAL писал(а):

Логик оказался на острове...

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

Пусть может быть, скажем, только 1 или 2 дома в деревне, если это так, то метод даст правильный результат.
Пусть $p=0;1$ - правдивость туземца.
На вопрос-утверждение $a$ логика туземец отвечает значением (да-нет) утверждения $p=a$.
Действительно, если $p=0$, то $(p=a)=(\neg a)$, а если $p=1$, то $(p=a)=a$.
Пусть утверждение $b$ характеризует число домов в деревне туземца, скажем $b$="в твоей деревне один дом" дает $b=1$ если дом один и $b=0$ если два дома.

Вопрос-утверждение $a$ логика очевидно зависит только от двух утверждений: $p$ и $b$, то есть является одной из $2^{2\cdot2}=16$-ти логических функций от двух логических переменных $p$ и $b$.
Если среди этих функций найдется хотя бы одна, при которой утверждение-ответ $p=a(p,b)$ туземца существенно зависит только от переменной $b$, то есть если ответ эквивалентен утверждению $b$ либо утверждению $\neg b$, то решение существует.

Смотрим, функция $a=...$ (находим ответ, подставляя значения $p=0;1$):
- $0$ дает ответ $\neg p$ на вопрос "1=0?"
- $1$ дает ответ $p$ на вопрос "1=1?"
- $p$ дает ответ $1$ на вопрос "ты правдив?"
- $\neg p$ дает ответ $0$ на вопрос "ты лжив?"
- $b$ дает ответ $p=b$ на вопрос "в твоей деревне один дом?"
- $\neg b$ дает ответ $p\not=b$ на вопрос "в твоей деревне НЕ один дом?"
- $p\vee b$ дает ответ $p\vee\neg b$ на вопрос "ты правдив, или в твоей деревне один дом?"~"если ты лжив, то в твоей деревне один дом?"~"если в твоей деревне не один дом, ты правдив?
- $p\vee\neg b$ дает ответ $p\vee b$ на вопрос "ты правдив, или в твоей деревне не один дом?"~"если ты лжив, то в твоей деревне не один дом?"~"если в твоей деревне один дом, ты правдив?
- $\neg p\vee b$ дает ответ $p\wedge b$ на вопрос "ты лжив, или в твоей деревне один дом?"~"если ты правдив, то в твоей деревне один дом?"~"если в твоей деревне не один дом, ты лжив?
- $\neg p\vee\neg b$ дает ответ $p\wedge\neg b$ на вопрос "ты лжив, или в твоей деревне не один дом?"~"если ты правдив, то в твоей деревне не один дом?"~"если в твоей деревне один дом, ты лжив?
- $p\wedge b$ дает ответ $\neg p\vee b$ на вопрос "ты правдив, и в твоей деревне один дом?"
- $p\wedge\neg b$ дает ответ $\neg p\vee\neg b$ на вопрос "ты правдив, и в твоей деревне не один дом?"
- $\neg p\wedge b$ дает ответ $\neg p\wedge\neg b$ на вопрос "ты лжив, и в твоей деревне один дом?"
- $\neg p\wedge\neg b$ дает ответ $\neg p\wedge b$ на вопрос "ты лжив, и в твоей деревне не один дом?"
- $p=b$ дает ответ $b$ на вопрос "то, что ты правдив также верно, как и то, что в твоей деревне один дом?"~"если я спрошу тебя: в твоей деревне один дом? - ты ответишь: да?"
- $p\not=b$ или же $p=\neg b$ дает ответ $\neg b$ на вопрос "то, что ты лжив верно также, как и то, что в твоей деревне один дом?"~"если я спрошу тебя: в твоей деревне не один дом? - ты ответишь: да?"

Как видно, в качестве ответа можно получить любую из функций (отображение $a\to(p=a)$ - биекция), а в нашем случае подходят два последних вопроса: $p=b$ и $p\not=b$ - ответу $b$ на первый логик должен воспринимать как истинный ответ на вопрос $b?$, а ответу $\neg b$ на второй из - как ложный ответ на этот вопрос.

Если количество возможных значений числа домов в деревне туземца более двух, то ответ гарантировано узнать НЕВОЗМОЖНО!
Конечно, если логику известно число домов $n$ и он хочет это число подтвердить, то ему следует взять $b$="в твоей деревне $n$ домов", но, см. пункт 3:

VAL писал(а):

3. Путешественник заранее не знает, сколько домов в деревне туземца.

и не может угадать его случайно в силу пункта 4:

VAL писал(а):

4. Путешественник не угадал случайно, сколько домов в деревне туземца.

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

nikov писал(а):

Не нужно умалчивать, что логик получает еще любое количество визуальной информации о поведении туземца.

Логик не может заставить туземца что либо делать, кроме как отвечать "Да-Нет" на устный вопрос-утверждение:
Туземец не должен подчинятся вопросу-приказу: "подпрыгни столько раз, сколько домов в твоей деревне и после ответь: ты лжец?".
На вопрос: "Есть ли в этой тетрадке (с числами по порядку, записанными через страницу) число домов в твоей деревне?" туземец не должен отвечать сразу, как только найдет это число в тетрадке - он может, не подавая виду, долиcтать тетрадку до конца и лишь затем ответить $p$ на вопрос с очевидно истинным ответом, а может и не отвечать вовсе, ибо это не устный вопрос - туземец вообще ничего не должен ни перелистывать, ни рассматривать - только слушать.
Также на вопрос: "Я буду называть тебе числа по-порядку, и когда назову число домов в твой деревне, ответь: столько ли домов в твоей деревне?" туземец не должен отвечать тогда, когда услышит число домов в своей деревне - он может дождаться конца вопроса, и только после этого ответить "столько ли домов в его деревне?", сколько было, когда логик произносил число домов в его деревне (это просто вопрос "n=n?") - мы лишь узнаем: лжец ли туземец.

[VAL]

ddn в сообщении #168640 писал(а):

Если количество возможных значений числа домов в деревне туземца более двух, то ответ гарантировано узнать НЕВОЗМОЖНО!

Ваши рассуждения весьма убедительны.
И все же задача имеет решение.
Я ведь не случайно назвал ее удивительной и потрясающей.

[Nxx]

TOTAL писал(а):

Nxx писал(а):

Ну или вас двое?

Она ответит да. Как её зовут?

Значит, сказала правду и ее зовут Маша.

Цитата:

Оба варианта не позволят узнать, кто Маша, кто Даша.

Оба варианта позволят.

В этой комнате две девочки?

В этой комнате есть Маша?


Элементарно.

[TOTAL]

Непонятно условие. Сколько деревень на острове. Каждый туземец живет в своей деревне?
Лжецы живут в одной деревне, а правдивые во второй?
Каждый туземец живет в своем доме?

Добавлено спустя 10 минут 57 секунд:

VAL писал(а):

Ваши рассуждения весьма убедительны.
И все же задача имеет решение.
Я ведь не случайно назвал ее удивительной и потрясающей.

Или такой же некорректной, как и задача с Машей и Дашей. В условии не сказано, что Маша знает, первой она отвечает или второй. А на этом знании основывается решение.

Вот и в задаче про остров тоже начали говорить про какую-то визуальную информацию.