forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Загадки (http://forum.boolean.name/forumdisplay.php?f=87)
-   -   Миссионер, заблудившийся в Южной Калифорнии (http://forum.boolean.name/showthread.php?t=17796)

impersonalis 27.01.2013 02:15
Миссионер, заблудившийся в Южной Калифорнии
 
Вложений: 3
Задача позаимствована из книги Э. Таненбаума "Архитектура компьютера" (5-е издание)
Цитата:
Миссионер, заблудившийся в Южной Калифорнии, остановился на развилке дороги. Он знает, что в этом районе обитают две мотоциклетные банды. Одна из них всегда говорит правду, а другая всегда лжёт. Он хочет узнать, какая дорога ведёт в Диснейленд. Какой вопрос он должен задать?
Ответы постить в OFFTOP-тег: не ломайте кайф остальным!
Искать непосредственно решение в интернетах - не комильфо.

Мой ответ:

ВНИМАНИЕ - ДАЛЕЕ ОТВЕТ:
Изначально, я вообще не собирался решать эту задачу (придумал первый попавшийся алгоритм - и успокоился). Но, забавы ради, кинул её Джокеру.
Общее решение было примерно следующим: задать составной вопрос, содержащий в себе маркер - подвопрос, ответ на который индицирует тип банды, позволив определить истинность ответа на второй подвопрос.
Маркером может выступать любое априорное знание: например, факт нахождения спрашивающего в Южной Калифорнии.

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

Сразу обратим внимание, что нам достаточно знать: выводит ли к цели ОДНА, фиксированная дорога (например, левая) - характеристика второй, получается очевидным образом. LEFT=1-RIGHT.
Итак, как работает банда? Мы можем задать ей некий вопрос, например: "Эта дорога выведет меня к Диснейленду?". Если банда ЛЖЁТ, то ответ буден инвертирован, а если нет - выдан без изменений. Схема на логических элементах выглядит, например, так:
Вложение 18537
Нетрудно составить таблицу значений функции:
(Ответ - О; Лгать - Л; Выход - В)
ОЛ В
00 0
01 1
10 1
11 0
По таблице легко заметить, что перед нами обычный XOR или сложение по модулю два.
Типовой пример взаимодействия с неизвестной бандой можно изобразить следующим образом:
Вложение 18538
Даже спросив по отдельности первую и вторую банду мы ничего не узнаем, кроме априорного: ответы будут противоположны.
Суть решения сводится к тому, что в совокупности на две банды, сигнал искажается единожды. Таким образом, собрав цепь из последовательно включённых банд, мы получим всего-лишь одну инверсию. Возможные варианты:
1. Ложь(Правда(Факт))
2. Правда(Ложь(Факт))
Нетрудно заметить, что Ложь и Правда действуют на бистабильный ответ подобно умножению на "один" и "минус один": минус на плюс - даёт минус, плюс на минус - минус, минус на минус - плюс. Иными словами: солгать правду - лгать, не перевирать ложь - лгать, искажать ложь - говорить правду.
Как реализовать это в схеме? Ведь мы можем опросить только одну банду. Нам требуется пропустить через фильтр одной банды, ответ другой. Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники?
Если перед нами лгуны, то ситуация: Ложь(Правда(Факт)). В противном случае: Правда(Ложь(Факт)). Как видим: "минус на плюс" и "плюс на минус", соответственно. В обоих ситуациях мы получаем лживый ответ. Осталось только его инвертировать.
Реализовать в схеме "что ответили бы на вопрос ваши соперники" можно инвертировав сигнал УПРАВЛЕНИЕ РЕЖИМОМ ЛЖИ и подав его в типовую схему банды с предыдущего рисунка. Затем пропустим выход через банду, стоящую перед нами, и, наконец, инвертируем ответ.
Вложение 18539
Так ли это на самом деле? Покажем это с помощью таблицы истинности.
(Ответ - О; Режим Текущей Банды - РТБ; Инверсия РТБ - ИРТБ; Ответ Конкурентов - ОК; Ответ Банды - ОБ; Результат - Р)
О РТБ ИРТБ ОК ОБ Р
0.0..1...1..1....0
0.1..0...0..1....0
1.0..1...0..0....1
1.1..0...1..0....1
Как видно, значения вектора О совпадают со значениями вектора Р.
Докажем верность решения, упростив выражение, формально описывающее работу схемы:
ANS=NOT( ( NOT(U) XOR A ) XOR U ).
Здесь U - Режим Текущей Банды, A - Факт.
Нетрудно заметить, что отрицание XOR даёт эквиваленцию. Последнее можно заключить как из определения операции, так и инвертировав вектор "выходных значений" XOR (0110 -> 1001) и подобрав (или поняв, посмотрев на носитель функции) подходящую новую функцию.
Следовательно:
ANS=NOT( NOT(U) XOR A ) EQ NOT(U)=
=( NOT(NOT(U)) EQ NOT(A) ) EQ NOT(U)=
=( U EQ NOT(A) ) EQ NOT(U).
Я так и не смог отыскать упоминания того, что для эквиваленции справедлива ассоциативность, поэтому я тупо сверил носители функций (A EQ B) EQ C и (A EQ C) EQ B. В общем, можно упростить далее:
ANS= U EQ NOT(U) EQ NOT(A)
Очевидно, что U EQ NOT(U) тождественно равно ЛЖИ.
ANS= 0 EQ NOT(A)
Эквиваленция лжи соответствует унарной операции инверсии операнда. Это обстоятельство можно получить или из анализа таблицы истинности, или из определения: действительно, истинно равной (=1) лжи, может быть только ложь (0), и наоборот неравной лжи (=0) может быть только истина (1)
ANS= NOT(NOT(A))=A.

Ответ:
Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники? Выберем вторую (другую) дорогу.

jimon 27.01.2013 03:05
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 

1) спросить у первой банды
2) получить пиздюлей
3) спросить у второй банды
4) получить пиздюлей
5) придумать хитрожопый соц. эксперимент (как Импер например)
6) провести эксперимент на бандах
7) получить пиздюлей
8) подумать, проверить календарь - там 2013 год
9) посмотреть по GPS\карте или спросить по телефону
10) ....
11) PROFIT !

den 27.01.2013 12:09
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Цитата:
Одна из них всегда говорит правду, а другая всегда лжёт.
Спросить, сколько будет "2+2" ? Та банда которая всегда говорить правду скажет "4", та которая всегда врет, всё что угодно, но не "4". Спросить у той которая сказала "4" дорогу в диснейленд.

Mr_F_ 27.01.2013 12:25
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 

Цитата:
Спросить, сколько будет "2+2" ?
Цитата:
получить пиздюлей
они же не обязаны отвечать на все твои тупые вопросы. думаю если задашь большинству пешеходов такой вопрос, ответ будет "дурак шоле?", и это не правда/ложь а тупо отказ от ответа

SBJoker 27.01.2013 13:15
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Цитата:
Сообщение от Den (Сообщение 250852)

Спросить, сколько будет "2+2" ? Та банда которая всегда говорить правду скажет "4", та которая всегда врет, всё что угодно, но не "4". Спросить у той которая сказала "4" дорогу в диснейленд.
В условии число вопросов ограничено одним.
Т.е. или узнать кто врёт или спросить дорогу.

BlackDragon 27.01.2013 13:33
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
"Пацаны, до Диснейленда подбросте. По братски, а?"

Dream 27.01.2013 16:37
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Цитата:
Сообщение от SBJoker (Сообщение 250858)
В условии число вопросов ограничено одним.
Т.е. или узнать кто врёт или спросить дорогу.
Ну так, если они сказали не 4 - значит они врут и вторая банда скажет точно какая дорога правильная. а если сказали 4. зеначит спросить у другой банды какая дорого и сделать наоборот же

SBJoker 27.01.2013 18:56
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Цитата:
Сообщение от Dream (Сообщение 250870)
Ну так, если они сказали не 4 - значит они врут и вторая банда скажет точно какая дорога правильная. а если сказали 4. зеначит спросить у другой банды какая дорого и сделать наоборот же
Повторяю, есть всего одна попытка спросить, и разговариваем мы по условию с одной бандой, но не известно с какой.

MiXaeL 28.01.2013 13:28
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Это же детский сад вроде, нет? Ответ, а точнее вопрос: "Что скажет другая банда, если я спрошу дорогу у них в Диснейленд?" Сами догадаетесь, почему надо выбрать другую дорогу.
Ответы не читал, может кто уже так и ответил.

Nerd 28.01.2013 13:44
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Миссионер небось исламистский, и едет в Диснейленд творить справедливость.

pax 28.01.2013 15:12
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
У меня появился другой вопрос - раз он заблудился, откуда знает столько про местные банды?.

MiXaeL 28.01.2013 16:13
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Цитата:
Сообщение от pax (Сообщение 250946)
У меня появился другой вопрос - раз он заблудился, откуда знает столько про местные банды?.
Наверняка у развилки табличка с описанием местных банд.

tormoz 28.01.2013 19:39
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
Миссионеры - зло.

k(void) 29.01.2013 00:30
Ответ: Миссионер, заблудившийся в Южной Калифорнии
 
По информации из википедии
Климат штата субтропический, часть территории занимает Нижнекалифорнийская пустыня. Умеренные ветры с Тихого океана и холодного Калифорнийского течения делают климат вдоль тихоокеанского побережья приятным круглый год. Дождей мало. Холодное океаническое Калифорнийское течение часто является причиной густых туманов на побережье. В горах наблюдается альпийский климат. Лето здесь прохладное, а зимы могут быть холодными, а ночью температуры часто опускаются ниже 0 °С. В горах часто выпадает и долго не тает снег с декабря по апрель. Восточная сторона полуострова – весьма засушлива. Далее на юг вдоль побережья засушливый климат сохраняется, но он становится мягче и не таким жарким. Осадков выпадает мало, в среднем 300 – 600 мм в год. На островах в Калифорнийском заливе – пустыни.

У миссионера обезвоживание, ему развилки и банды байкеров мерещатся...


Часовой пояс GMT +4, время: 16:16.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot