На распутье

Некий путешественник однажды оказался на острове, который населяли племя лжецов и племя правдивых туземцев. Члены первого племени всегда лгали, члены второго — всегда говорили только правду. Путешественник дошёл до места, где дорога раздваивалась, и вынужден был спросить у оказавшегося поблизости туземца, какая из двух дорог ведёт в деревню. Узнать, кем был встреченный туземец — лжецом или правдивым человеком, — путешественник не мог. Всё же, поразмыслив, он задал туземцу один-единственный вопрос и, получив ответ, узнал, по какой дороге следует идти. Какой вопрос задал путешественник?

Подход к решению этой задачи заключается в том, чтобы своим вопросом заставить лжеца солгать дважды и тем самым сказать правду. Например, путешественник может указать на одну из дорог и спросить туземца: «Если бы я спросил, ведёт ли эта дорога в деревню, вы бы сказали „да“?» Если бы туземец говорил только правду, то он бы ответил «да» в том случае, если бы дорога действительно вела в деревню, и «нет» в противном случае. Хитрость заключается в том, что и лжец будет вынужден отвечать точно так же!

Действительно, если дорога ведёт в деревню, то на прямой вопрос «ведёт ли эта дорога в деревню?» лжец бы ответил «нет», значит, отвечая на вопрос путешественника, он должен соврать, то есть ответить «да». Аналогично, если дорога не ведёт в деревню, то лжец должен ответить «нет».

Интересно, что задача имеет решение, даже если путешественник, в совершенстве владея языком туземцев, вдруг забыл бы, какое из двух слов (скажем, «пиш» или «таш») означает «да», а какое — «нет». В этом случае он должен указать на одну из дорог и спросить у туземца: «Если бы я спросил, ведёт ли эта дорога в деревню, вы бы ответили „пиш“?» Если островитянин отвечает «пиш», то путешественник может быть уверен, что выбранная им дорога действительно ведёт в деревню, даже в том случае, если он не уверен ни в том, с кем разговаривает, ни в том, что означает слово «пиш» — «да» или «нет». Если же туземец отвечает «таш», то путешественник делает обратный вывод.