![](images/chestnut/misc/left.gif) |
Загадки Постим и отгадываем загадки. Флуд запрещён - только условия и обсуждение решений. |
27.01.2013, 02:15
|
#1
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Миссионер, заблудившийся в Южной Калифорнии
Задача позаимствована из книги Э. Таненбаума "Архитектура компьютера" (5-е издание)
Миссионер, заблудившийся в Южной Калифорнии, остановился на развилке дороги. Он знает, что в этом районе обитают две мотоциклетные банды. Одна из них всегда говорит правду, а другая всегда лжёт. Он хочет узнать, какая дорога ведёт в Диснейленд. Какой вопрос он должен задать?
|
Ответы постить в OFFTOP-тег: не ломайте кайф остальным!
Искать непосредственно решение в интернетах - не комильфо.
Мой ответ:
ВНИМАНИЕ - ДАЛЕЕ ОТВЕТ:
Изначально, я вообще не собирался решать эту задачу (придумал первый попавшийся алгоритм - и успокоился). Но, забавы ради, кинул её Джокеру.
Общее решение было примерно следующим: задать составной вопрос, содержащий в себе маркер - подвопрос, ответ на который индицирует тип банды, позволив определить истинность ответа на второй подвопрос.
Маркером может выступать любое априорное знание: например, факт нахождения спрашивающего в Южной Калифорнии.
Однако скоро, мне вывалили иное решение. Без доказательства, но однозначно работающее. Учитывая специфику книги, я попробовал восстановить ход мыслей, дающих красивое решение.
Сразу обратим внимание, что нам достаточно знать: выводит ли к цели ОДНА, фиксированная дорога (например, левая) - характеристика второй, получается очевидным образом. LEFT=1-RIGHT.
Итак, как работает банда? Мы можем задать ей некий вопрос, например: "Эта дорога выведет меня к Диснейленду?". Если банда ЛЖЁТ, то ответ буден инвертирован, а если нет - выдан без изменений. Схема на логических элементах выглядит, например, так:
![Нажмите на изображение для увеличения
Название: схема_банды.jpg
Просмотров: 1771
Размер: 31.3 Кб
ID: 18537](https://forum.boolean.name/attachment.php?attachmentid=18537&thumb=1&d=1359231595)
Нетрудно составить таблицу значений функции:
(Ответ - О; Лгать - Л; Выход - В)
ОЛ В
00 0
01 1
10 1
11 0
По таблице легко заметить, что перед нами обычный XOR или сложение по модулю два.
Типовой пример взаимодействия с неизвестной бандой можно изобразить следующим образом:
![Нажмите на изображение для увеличения
Название: схема_банды_xor.jpg
Просмотров: 1634
Размер: 23.5 Кб
ID: 18538](https://forum.boolean.name/attachment.php?attachmentid=18538&thumb=1&d=1359231836)
Даже спросив по отдельности первую и вторую банду мы ничего не узнаем, кроме априорного: ответы будут противоположны.
Суть решения сводится к тому, что в совокупности на две банды, сигнал искажается единожды. Таким образом, собрав цепь из последовательно включённых банд, мы получим всего-лишь одну инверсию. Возможные варианты:
1. Ложь(Правда(Факт))
2. Правда(Ложь(Факт))
Нетрудно заметить, что Ложь и Правда действуют на бистабильный ответ подобно умножению на "один" и "минус один": минус на плюс - даёт минус, плюс на минус - минус, минус на минус - плюс. Иными словами: солгать правду - лгать, не перевирать ложь - лгать, искажать ложь - говорить правду.
Как реализовать это в схеме? Ведь мы можем опросить только одну банду. Нам требуется пропустить через фильтр одной банды, ответ другой. Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники?
Если перед нами лгуны, то ситуация: Ложь(Правда(Факт)). В противном случае: Правда(Ложь(Факт)). Как видим: "минус на плюс" и "плюс на минус", соответственно. В обоих ситуациях мы получаем лживый ответ. Осталось только его инвертировать.
Реализовать в схеме "что ответили бы на вопрос ваши соперники" можно инвертировав сигнал УПРАВЛЕНИЕ РЕЖИМОМ ЛЖИ и подав его в типовую схему банды с предыдущего рисунка. Затем пропустим выход через банду, стоящую перед нами, и, наконец, инвертируем ответ.
![Нажмите на изображение для увеличения
Название: схема_результат.jpg
Просмотров: 1704
Размер: 37.3 Кб
ID: 18539](https://forum.boolean.name/attachment.php?attachmentid=18539&thumb=1&d=1359232841)
Так ли это на самом деле? Покажем это с помощью таблицы истинности.
(Ответ - О; Режим Текущей Банды - РТБ; Инверсия РТБ - ИРТБ; Ответ Конкурентов - ОК; Ответ Банды - ОБ; Результат - Р)
О РТБ ИРТБ ОК ОБ Р
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.
Ответ:
Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники? Выберем вторую (другую) дорогу.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
|
|
27.01.2013, 03:05
|
#2
|
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
1) спросить у первой банды
2) получить пиздюлей
3) спросить у второй банды
4) получить пиздюлей
5) придумать хитрожопый соц. эксперимент (как Импер например)
6) провести эксперимент на бандах
7) получить пиздюлей
8) подумать, проверить календарь - там 2013 год
9) посмотреть по GPS\карте или спросить по телефону
10) ....
11) PROFIT !
|
|
|
Эти 7 пользователя(ей) сказали Спасибо за это полезное сообщение:
|
|
27.01.2013, 12:09
|
#3
|
Дэвелопер
Регистрация: 13.02.2010
Сообщений: 1,645
Написано 620 полезных сообщений (для 2,419 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Одна из них всегда говорит правду, а другая всегда лжёт.
|
Спросить, сколько будет "2+2" ? Та банда которая всегда говорить правду скажет "4", та которая всегда врет, всё что угодно, но не "4". Спросить у той которая сказала "4" дорогу в диснейленд.
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо den за это полезное сообщение:
|
|
27.01.2013, 12:25
|
#4
|
Терабайт исходников
Регистрация: 13.09.2008
Сообщений: 3,947
Написано 2,189 полезных сообщений (для 6,051 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Спросить, сколько будет "2+2" ?
|
они же не обязаны отвечать на все твои тупые вопросы. думаю если задашь большинству пешеходов такой вопрос, ответ будет "дурак шоле?", и это не правда/ложь а тупо отказ от ответа
|
(Offline)
|
|
27.01.2013, 13:15
|
#5
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Сообщение от Den
Спросить, сколько будет "2+2" ? Та банда которая всегда говорить правду скажет "4", та которая всегда врет, всё что угодно, но не "4". Спросить у той которая сказала "4" дорогу в диснейленд.
|
В условии число вопросов ограничено одним.
Т.е. или узнать кто врёт или спросить дорогу.
__________________
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо SBJoker за это полезное сообщение:
|
|
27.01.2013, 13:33
|
#6
|
Проектировщик
Регистрация: 25.03.2007
Сообщений: 536
Написано 252 полезных сообщений (для 715 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
"Пацаны, до Диснейленда подбросте. По братски, а?"
|
(Offline)
|
|
27.01.2013, 16:37
|
#7
|
быдло
Регистрация: 05.08.2007
Сообщений: 1,435
Написано 614 полезных сообщений (для 1,489 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Сообщение от SBJoker
В условии число вопросов ограничено одним.
Т.е. или узнать кто врёт или спросить дорогу.
|
Ну так, если они сказали не 4 - значит они врут и вторая банда скажет точно какая дорога правильная. а если сказали 4. зеначит спросить у другой банды какая дорого и сделать наоборот же
|
(Offline)
|
|
27.01.2013, 18:56
|
#8
|
Злобный Админ
Регистрация: 04.09.2005
Сообщений: 5,926
Написано 3,415 полезных сообщений (для 9,330 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Сообщение от Dream
Ну так, если они сказали не 4 - значит они врут и вторая банда скажет точно какая дорога правильная. а если сказали 4. зеначит спросить у другой банды какая дорого и сделать наоборот же
|
Повторяю, есть всего одна попытка спросить, и разговариваем мы по условию с одной бандой, но не известно с какой.
__________________
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо SBJoker за это полезное сообщение:
|
|
28.01.2013, 13:28
|
#9
|
Бывалый
Регистрация: 22.08.2006
Сообщений: 700
Написано 146 полезных сообщений (для 267 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Это же детский сад вроде, нет? Ответ, а точнее вопрос: "Что скажет другая банда, если я спрошу дорогу у них в Диснейленд?" Сами догадаетесь, почему надо выбрать другую дорогу.
Ответы не читал, может кто уже так и ответил.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
28.01.2013, 13:44
|
#10
|
Чудо-кот
Регистрация: 22.02.2011
Сообщений: 901
Написано 480 полезных сообщений (для 1,471 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Миссионер небось исламистский, и едет в Диснейленд творить справедливость.
|
(Offline)
|
|
28.01.2013, 15:12
|
#11
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
У меня появился другой вопрос - раз он заблудился, откуда знает столько про местные банды?.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
28.01.2013, 16:13
|
#12
|
Бывалый
Регистрация: 22.08.2006
Сообщений: 700
Написано 146 полезных сообщений (для 267 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Сообщение от pax
У меня появился другой вопрос - раз он заблудился, откуда знает столько про местные банды?.
|
Наверняка у развилки табличка с описанием местных банд.
|
(Offline)
|
|
28.01.2013, 19:39
|
#13
|
Гигант индустрии
Регистрация: 14.12.2005
Сообщений: 2,785
Написано 1,183 полезных сообщений (для 4,437 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
Миссионеры - зло.
|
(Offline)
|
|
29.01.2013, 00:30
|
#14
|
Hard airsofter
Регистрация: 10.10.2006
Адрес: В этой стране
Сообщений: 197
Написано 9 полезных сообщений (для 13 пользователей)
|
Ответ: Миссионер, заблудившийся в Южной Калифорнии
По информации из википедии
Климат штата субтропический, часть территории занимает Нижнекалифорнийская пустыня. Умеренные ветры с Тихого океана и холодного Калифорнийского течения делают климат вдоль тихоокеанского побережья приятным круглый год. Дождей мало. Холодное океаническое Калифорнийское течение часто является причиной густых туманов на побережье. В горах наблюдается альпийский климат. Лето здесь прохладное, а зимы могут быть холодными, а ночью температуры часто опускаются ниже 0 °С. В горах часто выпадает и долго не тает снег с декабря по апрель. Восточная сторона полуострова – весьма засушлива. Далее на юг вдоль побережья засушливый климат сохраняется, но он становится мягче и не таким жарким. Осадков выпадает мало, в среднем 300 – 600 мм в год. На островах в Калифорнийском заливе – пустыни.
У миссионера обезвоживание, ему развилки и банды байкеров мерещатся...
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 06:53.
|