Уильям Паундстоун - Как сдвинуть гору Фудзи

Эта идея — ключ к решению. Есть шанс, что, читая эти строки, вы воскликнете: «Я уже думал об этом! Ничего не получается!»

Дело в том, что это одна из тех хороших идей, которую легко испортить. Большинство людей подумает о том, чтобы начать с того, чтобы отправить Боно и Эджа вместе на другую сторону. И к чему это приведет?

У вас на другой стороне окажутся двое невыносимо медлительных людей с единственным фонариком. Это значит, что кому-то из них, вероятно Эджу, придется отправиться обратно (он пойдет медленно), чтобы переправить фонарик. На это уйдет пятнадцать минут, а еще трое людей, включая Эджа, не переправились через мост, и уже одно это не позволит этой троице переправиться за семнадцать минут.

Некоторые люди на этом и остановятся. Легко предположить, что подобное фиаско демонстрирует ложность ключевой идеи. Другие люди задумываются о том, не оставить ли этот переход пять/десять минут на самый конец. Последний переход особый, поскольку после него никому не нужно переправлять обратно фонарик.

Эта идея оказывается ничуть не лучше. Каким образом Эдж и Боно могут оказаться перед мостом с фонариком, когда двое других туристов уже переправились на другую сторону? Только если один из них (скорее всего Эдж?) уже побывал на той стороне и вернулся обратно с фонариком, но в этом случае на дорогу туда и обратно уже было потрачено десять минут, или фонарик вернул назад кто-то из их более проворных товарищей, но тогда он тоже ждет на этой стороне, чтобы переправиться. Это приводит к тем же проблемам, которые мы уже рассматривали раньше.

Вот тут многие люди и сдаются. Они исследовали два экстремальных варианта (медлительная пара переправляется первой или последней) и убедились, что они неэффективны.

Но эти крайние варианты — не единственная возможность. Медлительная пара может переправляться в середине. Вот что позволяет найти решение.

Цикл номер один: самая быстрая пара, Адам и Лари, переправляется через пропасть, потратив на это две минуты. Один из них (допустим, Адам — не важно, кто именно) немедленно возвращается обратно (на это уходит одна минута). На все это уйдет три минуты.

Цикл номер два: самая медленная пара, Эдж и Боно, переходят через мост, потратив десять минут. Как только они переправятся на другую сторону, они уже больше по мосту не путешествуют. Они передают фонарик более проворному товарищу, который уже там их поджидает (это Лари, предполагая, что Адам уже вернулся на исходный берег во время первого цикла). Лари приносит фонарик туда же (на это уйдет две минуты). Всего потрачено пятнадцать минут.

Наконец, последний третий цикл — переход только в одну сторону. Быстрая пара сейчас на исходной стороне. Они переходят пропасть во второй и последний раз (у них уходит на это две минуты). Всего потрачено семнадцать минут.

Корни этой головоломки можно обнаружить еще в раннем средневековье. Аббат Алкуин (735-804)[148] записал собрание головоломок, в которое вошла и ранняя версия хорошо знакомой многим головоломки о человеке, которому нужно было переправить через реку волка, козу и капусту. Козу нельзя оставлять вместе с волком, а козу — без присмотра вместе с капустой. За прошедшие с того времени двенадцать столетий было создано много вариаций на тему этой головоломки. Река иногда заменяется мостом, который вот-вот обвалится, или на блок, веревку и ведро, с помощью которых люди могут сбежать из башни. Ограничениями могут быть вес, время, запрет на то, чтобы оставлять женщин без присмотра, или уже упоминавшиеся выше отношения между хищником и его добычей. Головоломка о каннибалах и миссионерах, которым нужно переправиться через реку в двухместной лодке (в любой момент, когда каннибалов окажется больше, чем миссионеров, они съедят миссионеров), сыграла свою роль в первых исследованиях искусственного интеллекта. Уже первые программы ИИ смогли найти решение этой задачи.

Задача, используемая Microsoft, — одна из самых сложных в этом жанре. Она активно рассылалась по электронной почте в сопровождении своей «городской легенды». В этой легенде утверждалось, что «…один парень решил эту задачу, написав программу на языке С, правда, ему потребовалось на это 17 минут. Группа из 50 сотрудников компании Motorola так и не смогла ее решить… Обратите внимание: Microsoft требует, чтобы вы решили эту задачу не дольше, чем за 5 минут».[149] (На самом деле это не так.)

Перед вами две двери. Одна приведет вас в комнату, где вы пройдете интервью, а другая — на улицу…

Поскольку вы не знаете, скажет вам консультант правду или нет, бессмысленно задавать ему вопрос: «Это верная дверь?» или «Вы в этой компании работаете?» Вы получите ответ, который может оказаться и правдивым, и лживым. Используя свой единственный вопрос, вы не сумеет определить, правда это была или ложь. Вместо этого вам нужно придумать такой вопрос, что будет неважно, сказал консультант вам правду или солгал. Для этого нужно использовать двойное отрицание. К примеру, указать на дверь (не важно на какую) и сказать: «Если бы я спросил вас, этим ли путем я попаду на интервью, вы бы ответили да?»

Основная идея заключается в том, что законченный лжец солжет и насчет своего ответа на прямой вопрос о том, какая дверь приведет вас на интервью (который вы на самом деле ему не задавали!). Итак, законченный лжец скажет прямо противоположное тому, что бы он сказал, если бы ему задали прямой вопрос, то есть ложному ответу. Эти две лжи нейтрализуют одна другую, и получится, что лжец ответит вам «да» только в том случае, если вы указали на верную дверь. Что касается правдивого консультанта, то он тоже ответит «да» только если вы указали на верную дверь, потому что он, конечно, ответил бы так же и на прямой вопрос. Вы не узнаете, кто вам ответил — лжец или правдивый консультант, зато вы найдете нужную дверь.

Есть ряд альтернативных решений. Одно из них такое: «Если бы я спросил консультанта из другой фирмы, приведет ли эта дверь меня на интервью, он бы ответил утвердительно?» Все такие решения требуют, чтобы консультанты пожелали разобраться в подобных запутанных вопросах и дали на них ответ в том духе, в каком он ожидается. Но такие вопросы рискуют привлечь внимание лжеца к тому, что происходит нечто странное. Лучше, если лжец будет «безупречным лжецом», какие существуют только в логических головоломках. Если лжец будет действовать не так бездумно, как ожидается, и в первую очередь станет заботиться о том, чтобы обмануть, он может использовать тройное, а не двойное отрицание, чтобы сбить вас с толку.

Это можно обойти. Покажите на дверь и скажите: «Простите, я хотел бы пройти интервью в вашей компании — я попаду на него через эту дверь?»

Трюк с двойным отрицанием даст такой же результат, но данный вопрос звучит гораздо более естественно и позволяет лжецу солгать, не вдаваясь в сложный анализ. Это потому, что вам самому удается солгать (но только в том случае, если вы говорите с лжецом!), так как вы вовсе не хотите проходить интервью в фирме лжеца. Поэтому, если вы показываете на выход (который на самом деле как раз и может привести вас в фирму, где работает лжец, расположенную где-то на другом конце города), лжец солжет и скажет: «Нет, это не та дверь». А если вы покажете на дверь, которая должна на самом деле привести вас на интервью в нужной вам фирме, то есть на дверь, которая не приведет вас на интервью в конкурирующую фирму, на которую работает лжец, ему все равно придется солгать и сказать вам, что она туда приведет.

Эта версия «только с одним вопросом» старой загадки о лжеце и правдивом, похоже, появилась в 1950-е годы.[150] В той версии речь обычно шла о двух племенах правдивых и лживых, которые живут на далеком острове. Но была еще и несправедливо приписываемая Microsoft задача, которая активно распространялась в Интернете, предлагавшая новый поворот.[151] Вы оказались на перекрестке. Одна дорога ведет в Microsoft, другая — в фирму Utopia. Вы хотите попасть в Utopia. Вас встречает человек, у которого на голове коробка с Microsoft Windows. Вы не знаете, кто он — лжец, правдивый человек или Билл Гейтс. Вам разрешается задать ему только один вопрос. Какой это будет вопрос?

Когда эта задача появилась в тематической конференции rec.puzzles в Интернете, она вызвала целый шквал шутливых ответов, многие из которых были неистово «антимайкрософтовскими». Если вы считаете, что Билл Гейтс — сложная личность, о степени правдивости которой у нас нет никаких предположений, эта головоломка не имеет решения. Это все равно что заявить: «Вы оказались на острове Манхэттен, некоторые жители которого говорят правду, а некоторые — нет». Если же вы считаете, что Гейтс, что бы о нем ни говорили во время федерального расследования, не станет вас обманывать, когда вы попросите его указать дорогу, то он «считается» в этой головоломке честным и правдивым человеком, и тогда подходит прежнее решение.