Математическая логига

← →
Ricks © (2005-12-12 11:56) [0]

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

Присказка:
Как я тебе уже говорил, - начал Король, - в той далекой стране рыцари всегда говорили только правду и никогда не лгали, а лжецы всегда только лгали и никогда не говорили правды. Однажды все население страны пришло в необычайное волнение: стало известно, что в страну проник шпион из другой страны. - А как они об этом узнали? - спросила Алиса, позабыв о своем решении не перебивать Короля по пустякам. - Понятия не имею, - ответил Король, - к тому же это не имеет ни малейшего значения для задачи! - А шпион лгал или говорил правду? - спросила Алиса. - В том-то все и дело, что шпион не был ни рыцарем, ни лжецом. Иногда он говорил правду, иногда лгал в зависимости от того, как ему было удобнее.

И сама задача:
Относительно троих обвиняемых A, B и C суду и на этот раз известно, что один из них рыцарь, другой лжец, а третий шпион. Открывая судебное заседание, судья заявил, обращаясь к обвиняемым: - Сейчас я задам вам серию вопросов. На каждый вопрос следует отвечать кратко - "да" или "нет". Как только мне станет ясно, кто из вас шпион, я в тот же миг изобличу его, и процесс закончится. Как только мне станет ясно, что кто-то из вас заведомо не шпион, я тотчас же отпущу невиновного, не дожидаясь окончания процесса. Затем судья обратился к подсудимому A с вопросом: - Вы шпион? A ответил, после чего судья спросил подсудимого B: - Правду ли сказал A? B ответил. Судья немного подумал и спросил подсудимого C: - Вы шпион? C ответил, и судья тотчас же изобличил шпиона. Кто шпион? - Минуточку! - воскликнула Алиса. - Вы же не сообщили мне, что именно ответили судье обвиняемые. - Правильно, - согласился Король, - но эта задача особенная: ее можно решить, даже не зная, кто из подсудимых ответил "да" и кто "нет". Так кто же шпион?

Всего 48 вариантов решения (8 вариантов их ответов начиная с "нет, нет, нет" и до "да, да, да" плюс 6 перестановок Рыцарь Лжец Шпион)

После введения условий у меня из 48-и вариантов осталось 6

Но задача должна решаться однозначно!!!

Ваши предложения по этому поводу? :)

← →
umbra © (2005-12-12 11:58) [1]

Р. Смаллиан "Алиса в стране смекалки" (или как-то так). Поищите книжку.

← →
Sandman29 © (2005-12-12 12:06) [2]

Шпион B. Потому что:
1) А и С отвечали на один и тот же вопрос и выбрать среди них невозможно
2) Только шпион мог взять на себя смелость (и наглость :) отвечать на вопрос, на который он не может знать ответа.

← →
Ricks © (2005-12-12 13:15) [3]

> umbra ©

Да, это оттуда!
А что, там есть ответы?

Кстати, забыл сказать - ЭТО моя курсовая работа :)
И еще, препод говорил что в тексте могут быть ошибки.....

> Sandman29 ©

А как это сформулировать в терминах алгебры высказываний??? :)
Особенно "смелость" и "наглость" :)

← →
MBo © (2005-12-12 13:28) [4]

>А как это сформулировать в терминах алгебры высказываний??? :)

ключ в том, что судья смог принять решение

← →
Ricks © (2005-12-12 13:33) [5]

А какой же ключ?
Судья принял решение после того, как выслушал троих обвиняемых и не обязательно шпион C (как сказано в ответе http://golovolomka.hobby.ru/books/smullian/alice/otvet/50.htm)

← →
КаПиБаРа © (2005-12-12 14:54) [6]

Ricks © (12.12.05 13:33) [5]
А какой же ключ?

Такой, что этой информации ему хватило для точного определения. Если бы ответы были другие, то было бы больше 3-х вопросов.

← →
Гость1 (2005-12-13 10:06) [7]

Задачку можно решить "четко формализованным" методом без всяких демагогий :)

В постановке задачи даны два основных ключа:
1. Однозначность решения после трех ответов.
2.
> Как только мне станет ясно, что кто-то из вас заведомо не
> шпион, я тотчас же отпущу невиновного, не дожидаясь окончания
> процесса.

Никого не отпускали в ходе допроса.

← →
SergP. (2005-12-13 12:47) [8]

> После введения условий у меня из 48-и вариантов осталось
> 6

Напиши что у тебя осталось...

← →
Agent13 © (2005-12-13 13:43) [9]

Что меня смущает - это поведение шпиона. Как понимать
> Иногда
> он говорил правду, иногда лгал в зависимости от того, как
> ему было удобнее.

Значит ли это, что на вопрос "Шпион ли вы?" он всегда ответит "Нет" или же он настолько хитёр, что отвечая на вопрос продумывает как запутать судью? :)

← →
Гость1 (2005-12-13 14:04) [10]

> Agent13 © (13.12.05 13:43) [9]

> или же он настолько хитёр, что отвечая на вопрос продумывает
> как запутать судью? :)

Именно так.
Никаких ограничений на шпиона быть не должно.

← →
SergP. (2005-12-13 15:20) [11]

> Значит ли это, что на вопрос "Шпион ли вы?" он всегда ответит
> "Нет" или же он настолько хитёр, что отвечая на вопрос продумывает
> как запутать судью? :)

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

← →
Ya.ru (2005-12-14 12:49) [13]

> Ya.ru

:)
Все ни как не соберусь...

Осталось:
http://www.ricks.pisem.net/img.jpg
Надеюсь разберетесь...

← →
Гость1 (2005-12-14 13:51) [16]

Ответ С - шпион.

В общем, решение следующее:

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

Введем скоращения Р-рыцарь, Л-лжец, Ш-шпион, "-" - ответ нет, "+" - ответ да.

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

Таким образом, будем иметь следующее:

РЛШ : --- (0)
--+ (1)

РШЛ : --+ (1)
-++ (3)

ЛРШ : +-- (4)
+-+ (5)

ЛШР : +-- (4)
++- (6)

ШРЛ : --+ (1)
+++ (7)

ШЛР : -+- (2)
+-- (4)

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

Таким образом, получаем следующие возможные комбинации ответов:

РЛШ : --- (0)
РШЛ : -++ (3)
ЛРШ : +-+ (5)
ЛШР : ++- (6)
ШРЛ : +++ (7)
ШЛР : -+- (2)

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

Случай (3) имеет первыми двумя ответами -+, такую же комбинацию первых двух ответов, имеет только случай (2). Оба они однозачно определяют, что С - не шпион. Т.е. если бы такие комбинации имели место быть, то судья бы после второго ответа сразу бы отпустил С, этого не было, следовательно, данную комбинацию исключаем из рассмотрения. Аналогичным образом исключаем случаи (6) и (7).

Остаются случаи (0) и (5), в которых С - шпион.

Математическая логига Найти похожие ветки