Изначально, я вообще не собирался решать эту задачу (придумал первый попавшийся алгоритм - и успокоился). Но, забавы ради, кинул её Джокеру.
Общее решение было примерно следующим: задать составной вопрос, содержащий в себе маркер - подвопрос, ответ на который индицирует тип банды, позволив определить истинность ответа на второй подвопрос.
Маркером может выступать любое априорное знание: например, факт нахождения спрашивающего в Южной Калифорнии.
Однако скоро, мне вывалили иное решение. Без доказательства, но однозначно работающее. Учитывая специфику книги, я попробовал восстановить ход мыслей, дающих красивое решение.
Сразу обратим внимание, что нам достаточно знать: выводит ли к цели ОДНА, фиксированная дорога (например, левая) - характеристика второй, получается очевидным образом. LEFT=1-RIGHT.
Итак, как работает банда? Мы можем задать ей некий вопрос, например: "Эта дорога выведет меня к Диснейленду?". Если банда ЛЖЁТ, то ответ буден инвертирован, а если нет - выдан без изменений. Схема на логических элементах выглядит, например, так:
Нетрудно составить таблицу значений функции:
(Ответ - О; Лгать - Л; Выход - В)
ОЛ В
00 0
01 1
10 1
11 0
По таблице легко заметить, что перед нами обычный XOR или сложение по модулю два.
Типовой пример взаимодействия с неизвестной бандой можно изобразить следующим образом:
Даже спросив по отдельности первую и вторую банду мы ничего не узнаем, кроме априорного: ответы будут противоположны.
Суть решения сводится к тому, что в совокупности на две банды, сигнал искажается единожды. Таким образом, собрав цепь из последовательно включённых банд, мы получим всего-лишь одну инверсию. Возможные варианты:
1. Ложь(Правда(Факт))
2. Правда(Ложь(Факт))
Нетрудно заметить, что Ложь и Правда действуют на бистабильный ответ подобно умножению на "один" и "минус один": минус на плюс - даёт минус, плюс на минус - минус, минус на минус - плюс. Иными словами: солгать правду - лгать, не перевирать ложь - лгать, искажать ложь - говорить правду.
Как реализовать это в схеме? Ведь мы можем опросить только одну банду. Нам требуется пропустить через фильтр одной банды, ответ другой.
Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники?
Если перед нами лгуны, то ситуация: Ложь(Правда(Факт)). В противном случае: Правда(Ложь(Факт)). Как видим: "минус на плюс" и "плюс на минус", соответственно. В обоих ситуациях мы получаем лживый ответ. Осталось только его инвертировать.
Реализовать в схеме "что ответили бы на вопрос ваши соперники" можно инвертировав сигнал УПРАВЛЕНИЕ РЕЖИМОМ ЛЖИ и подав его в типовую схему банды с предыдущего рисунка. Затем пропустим выход через банду, стоящую перед нами, и, наконец, инвертируем ответ.
Так ли это на самом деле? Покажем это с помощью таблицы истинности.
(Ответ - О; Режим Текущей Банды - РТБ; Инверсия РТБ - ИРТБ; Ответ Конкурентов - ОК; Ответ Банды - ОБ; Результат - Р)
О РТБ ИРТБ ОК ОБ Р
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.
Ответ:
Спросим: что ответили бы на вопрос "выведет ли меня эта дорога к цели" ваши соперники? Выберем вторую (другую) дорогу.