Найти умного. Как проверить логическое мышление и творческие способности кандидата Паундстоун Уильям

У таких вопросов с подвохом может быть разная форма. Этот похож на детские картинки-загадки, на которых нужно отыскать спрятавшихся мальчиков или кошку. Нет общего правила поиска трюка – подобно кошке на загадочной картинке, трюк может быть спрятан где угодно. То, насколько быстро вы обнаружите трюк, зависит от того, на что вы обратите внимание в первую очередь, во вторую и третью. Ключевой множитель (X–X), естественно, «спрятан» там, где интервьюеры Microsoft ставят многоточие в выражении, которое нужно вычислить по условиям задачи.

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

? Разработайте систему счисления с основанием минус 2.

Эта глупая просьба долго использовалась в интервью, проводившихся в компании Microsoft. На самом деле нет никакого «минус двоичного» счисления. Это все равно, что попросить кого-нибудь написать несколько предложений на языке Клингонов – фантастической инопланетной расы из сериала Star Track.

Тем не менее можно изобрести логичную и последовательную систему счисления с основанием минус 2. Это как раз то, что от вас ожидается.

Мы пользуемся системой счисления с основанием 10. Это значит, что, когда мы записываем числа, мы представляем их как степени числа 10. Например, 176 – это 1 102 + 7 101 + 6 100. (Существует договоренность, что любое число в степени 0 равно 1.) Еще одна важная особенность десятичной системы счисления – это то, что в ней используется десять цифр (0, 1, 2, 3, 4, 5, 6, 7, 8 и 9).

Компьютеры используют систему счисления с основанием 2, или двоичную. В ней используются только две цифры (0 и 1). В многозначном числе (таком, как 10 010) каждый знак или позиция обозначает последовательные степени числа два – 1, 2, 4, 8, 16, 32… Двоичное число, например 10 010, означает 1 24 + 0 23 + 0 22 + 1 21 + 0 20. В обычной, десятичной системе счисления оно равно 18.

В общем, система счисления с любым основанием похожа на систему строительных блоков разных размеров. В десятичной системе размеры этих блоков 1, 10, 100, 1000 и т. д. В двоичной системе размеры блоков – 1, 2, 4, 8, 16 и т. д. Используя комбинации этих «блоков», можно получить любое нужное число.

Итак, какими будут обозначения в системе счисления с основанием минус 2?

Очевидно, что в этой системе счисления числа должны выражаться как суммы степеней числа –2. Последовательность степеней числа –2: –2, 4, –8, 16, –32…

Она отличается тем, что нечетные степени оказываются отрицательными (–2 –2 = +4, но –2 –2 –2 = –8). Таким образом, вам нужно выразить числа как сумму этих положительных и отрицательных степеней.

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

Перед тем как мы начнем считать, нужно решить еще одну проблему. Какие цифры мы станем использовать в минус двоичной системе? 2? 0 и 1? 0 и –1? Или нечто совершенно другое?

В системах с нормальным основанием количество цифр равно основанию. В десятичной системе десять цифр, в двоичной – только две цифры.

Если бы вы стали буквально следовать этому правилу, то пришли бы к заключению, что в минус-двоичной системе должно быть минус две цифры – это даже меньше, чем вообще ни одной цифры.

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

Наиболее очевидное решение использовать цифры 0 и 1. Это те же цифры, которые используются в обычной двоичной системе счисления. Альтернативное решение, возможно, более соответствующее духу минус двоичной системы счисления, – использовать цифры 0 и –1, причем последняя цифра должна восприниматься как единый символ. Хотя это несколько трудно и тяжеловесно. Остановимся на более простом варианте с цифрами 0 и 1.

Единицу можно просто записать как 1 (это значит 1 (–2)⁰).

С двойкой сложнее. Вторая позиция, считая справа налево, – это –2. Это значит, что 10 (в минус двоичной системе) будет 1 (–2)¹ + 0  (–2)⁰ = –2 + 0, или –2.

Попробуйте 111. Это 1 (–2)² + 1 (–2)¹ + 1 (–2)⁰ = 4 + (–2) + 1 = 3. Теперь замените единицу на ноль в первой справа позиции: 110 = 4 + (–2) + 0 = 2. Итак, вот что мы должны написать в минус двоичной системе для того, чтобы получилась двойка, – 110.

И мы только что выяснили, что тройка в минус двоичной системе – 111.

С четверкой все просто. Третья позиция – это 4, как и в обычной двоичной системе. Четыре записывается как 100.

Если вы поставите единицу в крайней справа позиции, то получится пятерка в минус двоичной системе, или 101.

Для того чтобы получилось шесть, не стоит ставить 1 во второй или четвертой позициях справа, так это дает негативные числа (соответственно –2 и –8). Вам нужно перепрыгнуть на пятую позицию, единица в которой обозначает +16. Таким образом, 10 000 – это 16. Это слишком много, но 11 000 – это 16 + (–8) = 8. Отнимите от этого числа двойку – для этого нужно поставить 1 во второй справа позиции (11 010), и вы запишете шестерку в минус двоичной системе.

Семерка получается, если добавить 1 в крайней правой позиции (11 011).

Мы уже раньше узнали, что 11 000 – это восемь.

Добавьте единицу в первой справа позиции – получите девять (11 001).

С десяткой придется повозиться. Начните с восьмерки (11 000). Добавьте к этому числу четыре, поставив 1 в третьей позиции (11 100). Теперь вычтите два, поставив 1 во второй позиции (11 110). Это и есть десять.

Итак, первые десять чисел в позиционной системе счисления с основанием минус 2 – это: 1, 110, 111, 100, 101, 11 010, 11 011, 11 000, 11 001 и 11 110.

? У вас два сосуда и 100 шариков…

На первый взгляд кажется, что изменить вероятность в ту или иную сторону невозможно. Количество красных и синих шариков абсолютно одинаково. Вам нужно все их использовать – нельзя «потерять» несколько синих шариков. Шарики достают абсолютно случайным образом. Разве шансы достать красный шарик не должны быть 50 на 50?

Так и будет, если вы положите 25 шариков каждого цвета в оба сосуда. Более того, вероятность будет 50 на 50, когда в каждом из сосудов по пятьдесят шариков независимо от того, в какой пропорции в каждом из них перемешаны цвета. Положите все красные шарики в сосуд А, а все синие – в сосуд В. И в том случае вероятность вытащить красный шарик в точности 50 %, потому что такова вероятность выбора сосуда А (а любой случайно выбранный из него шарик, как мы знаем, окажется красным).

Вот что может подсказать ответ на задау. Вам не нужно класть все 50 красных шариков в сосуд А. Достаточно положить туда всего один красный шарик: ведь и в этом случае вероятность того, что будет выбран сосуд А, остается 50 процентов. Тогда и в этом случае из него случайным образом будет «выбран» только красный шарик – учитывая, что выбирать-то там нечего.

Таким образом, уже только за счет сосуда А вероятность выбора красного шарика составит 50 процентов. Но у вас еще осталось 49 красных шариков, которые вы должны положить в сосуд вместе с 50 синими. В этом случае, если будет выбран сосуд В, шансы выбрать красный шарик из этого сосуда также будут почти 50 на 50 (в действительности эта вероятность равна 49 из 99). Таким образом, вероятность выбора красного шарика в целом (когда шарик случайным образом берется из одного из двух сосудов) будет чуть меньше 75 процентов (50 % + 1/2 от 49/99, а если сосчитать точно – 74,74 %).

Вот такой трюк используется при определении избирательных округов.

? У вас есть два ведра емкостью 3 литра и 5 литров и неограниченный запас воды. Как можно отмерить точно 4 литра воды?

Давайте подумаем о том, какое количество воды вы можете отмерить. Опустите 3-литровое ведро в колодец с неисчерпаемым запасом воды и вытащите его с водой: вот вам 3 литра воды. Проделайте то же самое с другим ведром – вот и еще 5 литров.

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

Если бы у вас был «не глаз, а алмаз», вы могли бы на глазок отлить точно 1 литр воды из 5-литрового ведра. Это и было бы решением задачи. Очевидно, так вы поступить не можете – иначе вам бы не задавали эту задачу.

Конечно, вы можете добавлять воду. Если бы вам удалось каким-то образом налить по 2 литра воды в 3-литровое ведро и в 5-литровое, то, перелив содержимое 3-литрового ведра в 5-литровое, вы бы получили ровно 4 литра воды.

Но, похоже, что эта операция ничего вам не дает. Вам даже никак не получить 3 + 3 = 6 литров воды, потому что в 5-литровом ведре 6 литров воды не поместится. Вы можете подумать о том, чтобы переливать отмеренное количество воды в ванну, пустой плавательный бассейн, пересохшее озеро – да куда угодно. Интервьюер не разрешит вам делать это. Вы можете представить, что находитесь на планете, которая вся покрыта океаном, и ваши два ведра – это единственные сосуды в этом мире.

Раз уж сложение не помогает решить эту задачу, вы можете попробовать использовать чуть более сложное действие, а именно вычитание. Налейте 5 литров воды в большее ведро, а затем аккуратно переливайте воду в 3-литровое ведро, пока оно не заполнится. А теперь стоп! Если вы ничего не пролили, то теперь у вас в 5-литровом ведре ровно 2 литра воды.

Если вы их оставите в 5-литровом ведре, то никогда не решите эту задачу. Единственный способ продвинуться в ее решении – опорожнить 3-литровое ведро и перелить два литра из 5-литрового ведра в 3-литровое.

Теперь вам нужно наполнить до краев 5-литровое ведро, а затем аккуратно отливать из него воду в 3-литровое ведро, пока оно не заполнится до краев. Таким способом вы отольете из 5-литрового ведра 1 литр воды, а это значит, что в нем останется 4 литра воды.

Альтернативное решение (для него потребуется переливать воду на один раз больше) – это наполнить 3-литровое ведро водой и перелить из него воду в 5-литровое ведро. Потом проделать это еще один раз и снова перелить воду в 5-литровое ведро, пока оно не заполнится до краев (тогда в 3-литровом ведре останется 1 литр воды). Теперь вылейте воду из 5-литрового ведра. Перелейте 1 литр воды в пустое 5-литровое ведро. Снова наполните 3-литровое ведро и перелейте из него воду в 5-литровое ведро, после чего в нем окажется 4 литра воды.

У.У. Раус Болл упоминает эту головоломку в своем сборнике «Математические досуги и эссе», 1892 год (Mathematical Recreations and Essays), популярном в викторианскую эпоху. Болл считал, что эту головоломку придумали в Средние века.

Хотя Льюис Терман использовал более простую версию этой задачи в своем первом тесте IQ (см. главу 2), он сообщал, что две трети «обычных взрослых людей» не успевали решить эту задачу за отведенные на это пять минут. «Если читателю покажется, что для решения этой задачи от него требуется слишком много изобретательности, – писал Терман, – стоит напомнить читателю, что в истории человечества важные изобретения не рождались неожиданно, подобно Минерве[12], но делались постепенно, шаг за шагом».

Минерва-Шминерва – версия задачи, использованная Терманом, действительно легкая. Это может отражать долговременную тенденцию увеличения «среднего» балла IQ (которую можно отметить, если вы используете для тестирования интеллекта тот же набор вопросов, что использовался в прошлом). В отличие от ожиданий Термана, среда оказывает существенное влияние на балл IQ.

Более трудная версия этой задачи, применявшаяся Microsoft, была использована в фильме «Крепкий орешек», 1995 год (Die Hard with a Vengeance). В этом фильме коварный преступник так настроил бомбу, что она должна была взорваться, если бы Брюс Уиллис и Сэмюель Л. Джексон не решили бы эту задачу. В их распоряжении был фонтан в парке и два пластмассовых ведра указанных размеров. Отмеренную воду нужно было поставить на весы. Они не могли гадать и действовать приблизительно, потому что бомба взорвалась бы даже если бы они ошиблись всего на одну унцию (28,3 грамма). Они не могли и просто уйти, потому что у бомбы был «детектор близости цели». Уиллис и Джексон смогли найти решение, да еще и дружески переругивались при этом («Я тебе не нравлюсь, потому что я белый!» / «Ты мне не нравишься, потому что я из-за тебя могу взлететь на воздух!»).

? Один из ваших работников настаивает на том, чтобы ему платили золотом каждый день…

Вам нужен один кусок золота, чтобы заплатить вашему работнику за первый день. Очевидный способ – отрезать один кусок от конца золотого слитка. Менее очевидный способ: отрезать этот кусок в середине слитка, использовав для этого оба разрешенных вам разреза. Попробуйте сначала очевидный план (оставив за собой право пересмотреть свое решение). Вы отрезаете один кусок от конца бруска и отдаете его работнику.

Это оставляет вам слиток, состоящий еще из шести кусков, и один разрез.

На второй день вы можете отрезать еще один кусок на конце слитка, но тогда у вас останется слиток из пяти кусков, а отрезать от него уже больше ничего нельзя. Вам нечем будет платить работнику на третий день.

Альтернативное решение – отрезать сегмент, состоящий из двух кусков. Тогда в конце второго дня вы можете отдать его работнику и получить от него назад один кусок как сдачу (при этом вы должны надеяться на то, что работник этот кусок еще не потратил).

Это оставит вас со слитком, состоящим из четырех кусков, одним куском, который вы получили как сдачу, а разрезов больше вы уже делать не можете. На третий день вы отдаете работнику один кусок. На четвертый день вы отдаете ему то, что осталось от слитка, то есть четыре куска, а два меньших он вам возвращает как сдачу. Затем вы аналогичным образом используете их, чтобы заплатить работнику на пятый, шестой и седьмой день.

? У вас есть b коробок и n банкнот в один доллар…

Основная идея решения аналогична той, что использовалась в задаче о золотом слитке. Вы используете бинарную систему счисления. Положите в первую коробку 1 доллар, во вторую 2, в третью – 4 и т. д. Любую нужную сумму можно представить как сумму различных степеней числа 2.

Отличие от приятной загадки с золотым бруском заключается в том, что данная головоломка проверяет, как вы «справляетесь с исключениями». Одна из сложностей связана с тем, что не все n оказываются суммой последовательных степеней числа 2. У вас, вероятно, образуется какой-то «остаток» денег после того, как вы разложите по коробкам все возможные для данного n последовательные степени числа 2. Еще одна проблема – вам может не хватить коробок.

Допустим, у вас 100 долларов. У вас будут коробки, в которые вы положите 1, 2, 4, 8, 16, 32 … доллара, но у вас окажется недостаточно денег для того, чтобы в следующую коробку положить 64 доллара, поскольку вы уже положили в предыдущие коробки 1 + 2 + 4 + 8 + 16 + 32 = 63 доллара. Это значит, что у вас есть остаток в 37 долларов, а это число – нечетное и никак не может быть степенью двойки.

Каким же образом вы сможете получить любую требуемую сумму от 0 долларов до 100? Используя первые шесть коробок, вы можете выплатить любую сумму от 0 до 63 долларов (чтобы выплатить 0 долларов, вы «передаете» ноль коробок!!!).

А что если вам нужно выплатить 64 доллара? Сначала вы отдаете седьмую коробку, в которой 37 долларов. Затем вычитаете 37 долларов из 64 долларов, и остается 27 долларов. Эту сумму вы можете выплатить, используя первые шесть коробок, суммы в которых соответствуют степеням числа 2. В данном конкретном случае вы отдаете коробки, сумма денег в которых равна 37, 16, 8, 2 и 1 доллару. Аналогичный принцип можно использовать для любой суммы в пределах 100 долларов.

Когда интервьюер спрашивает вас об «ограничениях» для b и n, он имеет в виду: «Каким образом вы можете определить, будет ли данный план работать для конкретных значений b и n?». Например, очевидно, что, если у вас есть миллион долларовых банкнот и всего одна коробка, такой план работать не будет. У вас недостаточно коробок для такой суммы. Обратите внимание, что обратная проблема вас не должна беспокоить: если у вас мало долларов и много коробок – все в порядке.

Вам нужно найти общую формулу, которая связывает b и n. Набросайте таблицу, показывающую, какую сумму вы можете выплатить, если у вас есть данное количество коробок.

b n

1 до 1 доллара

2 до 2 + 1 = 3 долларов

3 до 4 + 2 + 1 = 7 долларов

4 до 8 + 4 + 2 + 1 = 15 долларов.

Уже с первого взгляда видно, что добавление каждой новой коробки примерно удваивает количество денег, которое вы можете выплатить. Для двух коробок максимальная сумма 3 доллара, для трех коробок – 7 долларов. Если давать точный ответ, то b коробок достаточно для 2b 1-долларовых банкнот. Для того чтобы схема работала, n не должно превосходить 2b – 1.

Это приемлемый ответ. Он будет выглядеть немного более изящно, если вы добавите по 1 к правой и левой части: n + 1 < 2b. Это аналогично утверждению, что n должно быть меньше или равно 2b.

Как бы ни отражала эта загадка «цифровой дух нашего времени», она использовалась в той или иной форме еще со времен Ренессанса. Обычно ее называют задачей на взвешивание Баше, потому что она была упомянута в книге Клода Каспара Баше «Приятные и восхитительные задачи» (Problemes plaisans et dekctables), опубликованной в 1612 году. Баше спрашивал, какое минимальное количество гирь необходимо для того, чтобы уравновесить любой вес от 1 до 40 фунтов. Еще более ранняя версия этой задачи, тоже о взвешивании, была опубликована в трактате об измерениях Николо Тартальи в Венеции в 1556 году. Ответ, конечно, – 1, 2, 4, 8, 16 и 32 фунта. Для ренессансных гуманистов необходимость использования степеней числа 2 была гораздо менее очевидной, чем для интервьюеров из Microsoft, привычных к использованию двоичной системы счисления.

? У вас баночка, в которой драже трех цветов: красного, зеленого и синего…

Четыре. Если вы достаете только три драже – они могут все оказаться разных цветов. Если вы берете четыре драже – по крайней мере два из них обязательно будут одинакового цвета.

Это вариация Microsoft на тему более старой задачи о том, сколько носков вам нужно достать из ящика комода в темноте, чтобы быть уверенными в том, что у вас будет пара, подходящая по цвету. В компании Bankers Trust, например, спрашивают именно о носках. Если носки могут быть двух цветов, то ответ, очевидно, три.

? У вас три корзины с фруктами…

Представьте, что вы взяли какой-то фрукт из корзины с надписью «Яблоки». Какую информацию это вам дает? Только один бит информации, который сообщает вам, яблоко это или апельсин. Допустим, это яблоко. Корзина, из которой вы его только что достали, с названием «Яблоки», не может быть на самом деле корзиной, где только яблоки. Если уж вы нашли там яблоко, это значит, что в данной корзине должны быть перемешаны яблоки с апельсинами. Прекрасно. Тогда у нас остаются две корзины. На одной из них надпись «Апельсины», а на другой – «Яблоки и апельсины». В корзине «Апельсины» не может быть апельсинов (потому что все ярлыки с названиями ложные), это не может быть и смесь яблок с апельсинами (мы ведь уже знаем, что это корзина с ярлыком «Яблоки», из которой мы достали яблоко). Таким образом, в корзине с ярлыком «Апельсины» должны быть только яблоки, и тогда в корзине с ярлыком «Яблоки и апельсины», очевидно, одни апельсины.

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

Вам нужно быть уверенным в том, что фрукт, который вы достали из корзины, даст вам понять, что в этой корзине. Единственный способ добиться этого – взять фрукт из корзины, на которой ярлык «Яблоки и апельсины». Поскольку все ярлыки неверные, там должны быть фрукты только одного типа. И, достав фрукт, вы знаете, какого именно.

Если это был апельсин, то в данной корзине только апельсины. Тогда у нас остаются две корзины с названиями «Яблоки» и «Апельсины». В одной из этих корзин действительно яблоки, а в другой – смесь. Снова, поскольку известно, что все ярлыки ложные, яблоки не могут находиться в корзине с названием «Яблоки» – они должны быть в корзине с надписью «Апельсины». Это значит, что смесь яблок и апельсинов находится в корзине с названием «Яблоки». Аналогичные рассуждения позволяют решить задачу, если вы достали из корзины с надписью «Яблоки и апельсины» яблоко.

? В деревне, где живет пятьдесят семейных пар, каждый из мужей изменял своей жене…

Начните с ситуации, которая существует в деревне до того, как королева сделала свое заявление. Вы знаете, что каждый мужчина изменял своей жене.

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

Все дело в том, что только жена неверного мужа обязана его убить. Каждая из женщин деревни знает об изменах мужей других сорока девяти женщин, но ничего не знает об изменах своего собственного мужа. Этикет исключает сообщение этого неприятного факта каждой из женщин.

Это, конечно, странная ситуация, но она вполне обычна для логических головоломок. Но однажды в деревню приезжает королева и говорит, что по крайней мере один муж неверен своей жене. Каким образом это изменит ситуацию?

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

Вот на чем попадаются многие кандидаты. Если заявление королевы неинформативно – о чем тут еще говорить? Ни одна женщина из-за этого не станет убивать своего мужа. Ничего не произойдет.

И предположение о том, что «ничего не произойдет», верно до конца того дня, когда королева сделала свое объявление.

Ничего не произойдет и на следующий день, и еще через день.

Давайте сразу перепрыгнем в сорок девятый день. Возьмем, к примеру, одну женщину по имени Эдна. Эдне известно об изменах сорока девяти мужей. Среди них есть и Макс – муж ее подруги Моники. Учитывая то, как быстро распространяются слухи, Эдна знает, что Монике должно быть известно (по меньшей мере) о сорока восьми неверных мужьях. Это те сорок восемь, о которых знает Эдна, минус Макс. Никто не осмелится рассказать Монике о проделках Макса.

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

Если бы в деревне был только один неверный муж, его жена должна была убить его в тот день, когда королева сделала свое объявление (назовем этот день первым). Так как в этом случае все женщины знали бы об этом единственном неверном муже за исключением его жены. Она была бы единственной женщиной, которой бы не было известно о неверном муже. Поэтому объявление королевы было бы для нее как удар грома. Поскольку она не знала ни о каких неверных мужьях, этот «по крайней мере» один неверный муж должен быть ее собственным мужем. Она должна была бы убить его в тот самый день, как предписано законом. Конечно, в том случае, если бы в деревне был всего один неверный муж.

Вместо этого настает утро второго дня – и все мужчины живы. Это информирует всех жителей в деревне о том, что неверных мужей более одного. И это, и безупречность королевы подразумевает, что неверных мужей должно быть по крайней мере два.

И если неверных мужей было бы только два, их жены убили бы их на второй день, а если бы их было три – жены бы убили их на третий день, и т. д. И если бы их было сорок восемь – их сорок восемь жен убили бы их на сорок восьмой день.

Сегодня уже сорок девятый день, и Моника, которая знает о сорока восьми неверных мужьях, должна быть удивлена тому, что в предыдущий день не произошло массового убийства. Единственное возможное объяснение (это все еще размышления Эдны о том, что должна была подумать Моника) – муж Моники как раз и есть сорок девятый герой адюльтера.

Таким образом, Эдна должна прийти к заключению, что всегда безупречно логичная Моника должна убить Макса к полуночи сорок девятого дня. Эдна может прийти к подобному же заключению относительно всех остальных женщин деревни. «Да, – думает Эдна, – на сорок девятый день произойдет кровавая баня».

И вот настал сорок девятый день, и все еще ничего не произошло. Единственное возможное объяснение теперь – это то, что Моника и все остальные женщины знали о сорок девятом неверном муже. Это не мог быть Макс. Это мог быть только один мужчина: собственный муж Эдны Эдгар!

Итак, на пятидесятый день Эдна должна прийти к заключению, что ее муж неверен ей. Все остальные женщины сделают о своих мужьях такой же вывод.

Ответ на головоломку – ничего не произойдет в первые сорок девять дней, а на пятидесятый день все пятьдесят жен убьют своих мужей.

Это шедевр среди логических головоломок. Однако нельзя с уверенностью утверждать, что эта задача так же хороша, как инструмент при отборе кандидатов на работу. Первое известное упоминание об этой головоломке в печати – опубликованная в 1958 году книга физика Джорджа Гамоу и математика Марвина Стерна «Математические головоломки» (Puzzle-Math). В их версии речь шла о неверных женах. С тех пор эта головоломка широко использовалась. К 1980-м годам речь уже идет о неверных мужьях, и головоломка становится темой исследования одной из научных лабораторий IBM. Джон Аллен Паулос дал в книге «Жило-было число» (Once upon a Number), опубликованной в 1998 году, версию, так похожую на ту, что используется Microsoft, что, возможно, корпорация использовала именно этот источник.

Я подозреваю, что типичный читатель этой книги прочитал головоломку, подумал о ней немного, не придя ни к какому выводу, и заглянул в ответ: «Вот это да! Какая замечательная головоломка!» Потом, возможно, загадал ее двум-трем друзьям, которые также не сумели ее решить, но согласились, что у нее потрясающее решение, когда узнали о нем. Популярность логической головоломки никак не зависит от того, может кто-то ее решить или нет.

Это становится проблемой только если кто-то пытается использовать данную головоломку для отбора кандидатов на работу. Хотя в причудливой «рекурсивной» логике, используемой для решения этой задачи, можно найти определенные параллели с программированием, эту головоломку очень трудно решить людям, которые понимают поведение реальных людей (а это полезное качество даже для программиста). Когда они не могут ее решить, это обычно происходит из-за того, что они приходят к верному заключению, что если уж ничего не происходит сразу после заявления королевы, то с течение времени драматизм ситуации будет только ослабевать. Обычно это вполне разумный вывод, если речь идет не о решении логических головоломок.

? Злобный демон поймал много гномов (их точное количество неизвестно)…

Какие выводы может сделать в этой ситуации безупречно логичный гном? Наверное, никаких. Скорее всего типичный гном видит других гномов с зелеными или красными камнями. Он все еще ничего не знает о том, какого цвета камень у него на лбу.

Но представьте, что есть гном, который видит только красные или только зеленые камни на лбу у других гномов. Поскольку демон сообщил всем гномам, что среди них есть хотя бы один такой, у которого красный камень на лбу, гном, который видит только зеленые камни, может прийти к выводу, что он и есть единственный гном с красным камнем. И наоборот: гном, который видит только красные камни, может заключить, что он – единственный гном с зеленым камнем на лбу.

Теперь подумайте о гипотетическом гноме, который видит вокруг только гномов с зелеными камнями. Он должен понять, что у него на лбу – красный камень. Все, что ему нужно сделать, – просто шагнуть вперед на следующей перекличке после объявления демона. Он может быть уверен в том, что его безупречно логичные товарищи останутся в строю. Это и будет правильным ответом, который потребовал демон.

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

Эти гномы остаются в строю, потому что им неизвестен цвет их собственного камня. Помните, если кто-то сделает неверный шаг, все гномы погибнут. Логика подсказывает, что единственное безопасное решение – оставаться в строю, если только гном не уверен в том, что у него на лбу красный камень.

Это еще не решение проблемы. Это только один из возможных сценариев, который проще всего анализировать. Это не значит, что именно это реальная ситуация: нам только сообщили, что гномов много, но неизвестно, сколько точно и красные у них на лбу камни или зеленые.

Если описанный выше сценарий не будет реализован во время первого построения (а скорее всего он не будет реализован), все гномы могут прийти к выводу, что есть по крайней мере два камня каждого из двух цветов. Это могло быть очевидно с самого начала (если бы все гномы видели много камней разного цвета), но, если бы был гном, который бы видел только один камень данного цвета, он мог бы во время второго построения прийти к выводу, что он – вторая персона с камнем этого цвета. Он и второй гном с камнем этого цвета (который рассуждает идентичным образом) сделают шаг вперед во время второго построения… Эта цепочка рассуждений и метарассуждений (рассуждений о рассуждениях) будет продолжаться, пока количество построений после объявления демона не совпадет с реальным количеством гномов с камнями более редкого цвета. На этом построении все безупречно логичные гномы с камнем этого цвета сделают шаг вперед, и (если демон держит свои обещания) все гномы обретут свободу.

Любому студенту, который изучает программирование, известно имя Алонзо Черча. В 1930-х годах Черч сформулировал так называемый тезис Черча – Тьюринга – краеугольный камень в исследованиях искусственного интеллекта (суть тезиса в том, что компьютер можно запрограммировать делать все то, что могут делать люди). Черч также один из немногих людей, которых можно обоснованно считать авторами логических головоломок мирового класса. Примерно в то же время, когда он сформулировал свой знаменитый тезис, он придумал головоломку о трех садовниках, у которых были пятна грязи на лбу. Их видит другой человек и замечает, что по крайней мере у одного из них грязь на лбу. Каждому из садовников нужно дедуцировать, грязный у него лоб или чистый.

Эта головоломка послужила вдохновением для целого жанра задач о людях, которые должны дедуцировать, какого цвета у них на голове шляпа или печать на лбу. В последние годы Раймонд Смаллиан предложил много вариаций хороших задач на эту тему. Тем или иным способом практически все эти головоломки решаются на основе предположений о поведении безупречно логичных существ, которые делают выводы на основе того, что их коллеги, также безупречно логичные существа, не делают определенного вывода в течение какого-то определенного срока.

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

? Четырем туристам нужно ночью переправиться через реку по подвесному мосту…

Никто не знает, почему у туристов имена музыкантов из группы U2.

Поскольку фонарик только один и без него никак не обойтись – единственный способ переправляться через мост такой: двое людей переходят на другую сторону, а потом одному из них нужно вернуться назад с фонариком. Чистый результат такого цикла – один человек переправляется через пропасть.

Когда два человека идут по мосту вместе, то общая скорость будет скоростью более медлительного из них. Если Адам переправляется вместе с Боно, то ему придется идти так же медленно, и этой паре потребуется для переправы через мост десять минут.

Вам может показаться, что для того, чтобы все четверо переправились, им понадобится четыре перехода туда и обратно. К счастью, это неверно.

Последний переход не требует возврата и позволяет переправиться через пропасть сразу двоим туристам. Таким образом, вам понадобятся два с половиной перехода туда и обратно, и в последний переход переправятся сразу двое.

Наиболее привлекательной идеей, пожалуй, представится такая: поручить Адаму, который переправляется через мост всего за одну минуту, сопровождать своих более медлительных друзей.

Во время первого перехода на другой берег пойдет Адам с самым медлительным из туристов Боно (ему нужно десять минут). Эта пара переправится за десять минут.

Потом Адам переправится обратно с фонариком (на это уйдет всего одна минута).

Теперь Адам пойдет через мост вместе со вторым медлительным спутником Эджем (которому требуется пять минут) и снова вернется назад (еще одна минута).

Наконец, через мост пойдут Адам и Лари (две минуты). Полное время: 10 + 1 + 5 + 1 + 2 = 19 минут. Это на две минуты дольше, чем требуется.

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

Попробуйте старый трюк и перечислите все ваши предположения. Самое основное из них – кто-то должен возвращаться, чтобы вернуть фонарик на тот берег, где его ждут спутники, верно?

Трудно понять, как можно разрешить эту проблему. В условии задачи четко говорится, что никто не может перейти мост без фонарика. (Если вы попробуете как-то «перехитрить» это условие, например перебросить фонарик через пропасть или использовать бечевку для перетаскивания фонарика через пропасть, интервьюер скажет вам, что это недопустимо.)

Мы также предположили, что два человека переправляются через пропасть, а назад возвращается один из них с фонариком. Может быть, стоит попробовать другие варианты?

Нет смысла совершать такие «переходы», которые никому не позволяют переправиться через пропасть. Кроме того, нам сказали, что трех людей (или больше) мост не выдержит. Это оставляет всего две возможности: по мосту идет один человек или два человека. Если вы и подумали о «полном цикле в обратную сторону», то есть это такой вариант, когда вы поручаете кому-то переправить обратно человека, уже перешедшего через пропасть, – в этом нет смысла. Мы вернулись к тому, с чего начинали.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Большинство решений, появившихся на rec.puzzles, были куда более творческими. Одно из них предлагало спросить того человека: «Куда я хочу сегодня пойти?» и сделать противоположное тому, что он ответит (на тех основаниях, «что они даже этого еще не поняли в Microsoft»). В другом решении предлагалось спросить у этого парня: «Какой путь мне посоветует выбрать человек из другого племени?» и затем стукнуть его. «Если этот человек – правдивый или лжец, вы узнаете от него, какая дорога ведет в Utopia, а если нет – вам удастся отвесить бесплатную оплеуху Биллу Гейтсу».

? Почему банки для пива сужаются вверху и внизу?

Если ваша догадка – это делает банки более прочными, то это, в общем, верно. Сужения вверху и внизу связаны с общей конструкцией банки. Это «архитектурный вопрос»: жестяные банки, как и подвесные мосты, работают как единое целое. Это часто означает, что нелегко дать конкретное объяснение, почему какая-то деталь выглядит именно так.

Если говорить об истории сужений – изначально они не были предназначены для того, чтобы банки были крепче. Банки и так были достаточно прочны, чтобы держать в них пиво. А что еще требуется от пивной банки? Сужения были элементом конструкции, который позволял уменьшить расход металла. Это может показаться пустяковой экономией, если только вы не задумаетесь о том, сколько банок выпускается и перерабатывается каждый год.

Было время, когда пиво и газированные безалкогольные напитки выпускали в тяжелых стальных банках, которые были в сечении почти прямоугольными. Сталь должна была быть достаточно толстой, чтобы выдержать давление газированных напитков. Эти банки изготавливались из трех частей, это значит, что закругленные верх и низ прикреплялись при помощи опрессовки к цилиндрической середине.

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

Самая толстая и прочная часть банки – это ее верх, который крепится при помощи обжима. Он должен выдерживать усилие при открывании банки. Поскольку металл верхней крышки банки толще, производитель заинтересован в том, чтобы минимизировать диаметр этой крышки, поэтому диаметр верха немного меньше, чем диаметр середины, и, чтобы их можно было соединить, банка должна сужаться вверху (нельзя уменьшить диаметр всей банки, потому что в нее тогда поместится меньше пива). Но раз уж вы сузили верх, вам придется сделать то же самое и с донышком, чтобы банки можно было ставить друг на друга.

Есть уже одна причина, по которой банка внизу сужается. Донышко и средняя часть банки прессуются из одного листа тонкого алюминия, что позволяет избежать дополнительной операции – крепления донышка к банке. Это проще сделать, если в нижней части банка идет на конус, чем если бы требовался изгиб под прямым углом. Это сужение также делает банку чуть более устойчивой к вмятинам на концах.

Похожий вопрос для интервью: «Почему дно банки для кока-колы вогнуто внутрь?» (У пивных банок такое же вогнутое донышко.) Ответ таков: металл на донышке настолько тонкий, что, если бы донышко было плоским, оно бы легко деформировалось. Вогнутый металл прочнее, чем плоский, точно так же, как выпуклая яичная скорлупа делает его более прочным по сравнению с яйцами, у которых была бы кубическая скорлупа. Прочность не зависит от того, вогнутое донышко или выпуклое, но, если бы донышки были выпуклыми, банки нельзя было бы ставить друг на друга.

? Сколько времени понадобится для того, чтобы передвинуть гору Фудзи?

Похоже, что этот вопрос был придуман в консалтинговой фирме Booz, Allen and Hamilton. Есть два возможных подхода к решению. Если вы решите передвинуть всю гору целиком – таким же способом, как европейские монархи заставляли своих инженеров перевозить в свои столицы египетские обелиски, я желаю вам удачи. В противном случае вы должны применить метод приблизительных вычислений Ферми. Для начала вы будете считать передвижение горы на новое место обычными земляными работами. Вам нужно оценить объем горы Фудзи «в самосвалах».

Отправной точкой для вычислений, вероятно, должен стать знаменитый силуэт горы Фудзи. Большинство американцев представляет его себе как полый конус, основание которого примерно в пять раз больше, чем высота. Большинство людей гораздо хуже может оценить высоту этой горы. Фудзи не может сравниться по этому параметру с самыми высокими горами (высота Эвереста около 29 000 футов, или 8848 метров). Но очевидно, что ее высота несколько тысяч футов. Давайте остановимся на удобном круглом числе 10 000 футов (это хорошая догадка, потому что на самом деле вершина горы Фудзи находится на высоте 12 387 футов над уровнем моря). Это значит, что высота нашего конуса 10 000 футов, а диаметр основания – 50 000 футов.

Если бы гора Фудзи была похожа не на конус, а на цилиндрическую жестянку, ее объем был бы равен произведению площади основания на высоту. Основание – это круг диаметром 50 000 футов. Квадрат со стороной 50 000 футов имел бы площадь 50 000 50 000 футов. Это 2,5 млрд квадратных футов. Но площадь круга, вписанного в подобный квадрат, будет меньше (если точно, то она составит /4 от площади квадрата, или 79 процентов), поэтому давайте оценим ее как 2 млрд квадратных футов. Умножьте это число на высоту 10 000 футов, и вы получите 20 трлн кубических футов – это будет объем цилиндра, в который можно вписать гору Фудзи.

Но гора Фудзи больше похожа на конус. Если вы помните, что объем конуса – это одна треть от объема цилиндра с таким же основанием и высотой, это делает вам честь. Но даже если вы этого не помните, очевидно, что объем конуса должен быть меньше, чем объем эквивалентного цилиндра. Поскольку мы так любим круглые цифры, давайте сократим 20 трлн кубических футов до 10 и будем считать, что объем конуса-горы Фудзи – 10 трлн кубических футов вулканических пород.

Сколько это самосвалов? Самосвал может перевезти объем скальных пород объемом 10 на 10 на 10 футов. Это 1000 кубических футов. Таким образом, для перевозки горы Фудзи потребуется нагрузить 10 млрд самосвалов.

Формулировка вопроса оставляет неопределенными многие параметры. Мы не знаем, куда мы передвигаем гору Фудзи. Попробуйте спросить об этом интервьюера. Мы также не знаем, какую долю объема горы составляет почва, которую легко погрузить экскаватором, а какую – твердые скальные породы, которые придется взрывать динамитом.

Даже в лучшем случае, чтобы нагрузить и перевезти один самосвал, потребуется полный рабочий день одного работника. Если считать, что один груз самосвала эквивалентен одному рабочему дню, то для того, чтобы передвинуть гору Фудзи, понадобится 10 млрд рабочих дней.

Длительность проекта будет зависеть от того, сколько людей станут выполнять эту работу. В абсолютно невероятном случае, если всю эту работу будет выполнять только один человек (естественно, таких людей придется после смерти заменять, подобно смотрителям маяков, на протяжении многих тысячелетий), для завершения работы понадобится 10 млрд дней, или примерно 30 млн лет. (Гора Фудзи, вероятно, столько времени и не существовала и вряд ли просуществует в своем нынешнем виде так долго. Она по естественным причинам исчезнет еще до того, как один человек сумеет ее передвинуть.)

Если будет реализован не менее невероятный вариант и удастся привлечь к этой работе все 6 миллиардов людей, населяющих земной шар (а также снабдить их необходимым оборудованием и сделать так, чтобы они не мешали друг другу), гору можно будет передвинуть за пару дней.

Представьте теперь, что правительство Японии решило передвинуть гору Фудзи и привлекло для решения этой задачи достаточно солидные ресурсы. 10 000 человек – примерно столько людей работает в больших корпорациях – это будет хорошая оценка. Им потребуется для решения задачи 10 млрд/10 000 дней. Это 1 млн дней, или примерно 3000 лет.

? В коридоре три выключателя…

Это еще одна задача, которая кажется не имеющей решения. Если вы выключите все выключатели, то свет не будет гореть (и ваш поход в комнату вам ничего не скажет). Если же вы включите один из выключателей, вероятность того, что вы выбрали нужный, – один к трем. Если повезет, то свет будет гореть, и вы найдете нужный выключатель, но в двух из трех случаев свет гореть не будет, и у вас не будет возможности определить, какой из двух выключенных выключателей включает свет в комнате. Если вы включите два из трех выключателей или все три, то столкнетесь со сходными проблемами.

Если по-другому это сформулировать: для идентификации одного объекта из трех нужны два бита информации. Ваш единственный визит в комнату дает вам только один бит информации.

Если бы это были выключатели, которые не просто включают или выключают свет, но регулируют его интенсивность, задачу было бы легко решить. Вы бы один из них включили на полную мощность, второй выключили бы, а третий включили бы на 50 процентов. Тогда состояние лампочки подсказало бы вам, какой из выключателей ее контролирует.

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

Вот решение: пронумеруйте выключатели 1, 2 и 3. Затем включите выключатели 1 и 2 и выключите выключатель номер 3. Подождите примерно десять минут. Затем выключите выключатель номер 1, включите выключатель номер 2 и немедленно отправляйтесь в комнату.

<>Если свет там горит, значит, его включает выключатель номер 2. Если свет не горит, но лампочка теплая, его контролирует выключатель номер 1. Если свет не горит и лампочка холодная, его контролирует выключатель 3.

? Вы играете в игру только с одним другим игроком…

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

Право первого хода обычно дает преимущество. Когда вы играете в крестики-нолики, вам выгодно поставить первый крестик в центральную клетку. Вам нужно задать себе вопрос: «Есть ли такой уникальный первый ход, который может дать мне стратегическое преимущество?»

В данном случае нет центральной клетки – есть бесконечное множество мест, куда вы можете положить свою первую монету. Предположим, вы решили положить ее в северо-западный угол стола на том основании, что это особая, если уже не уникальная позиция. Даст ли это вам стратегическое преимущество?

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

Не похоже, что занятие северо-западного угла стола даст вам уникальное стратегическое преимущество. Это не игра в «Монополию», где Променад дает вам более высокий доход, чем любая другая собственность. В нашем случае один угол ничем не лучше, чем любой другой. В действительности, если бы занятие угла давало бы какое-то преимущество, ваш противник ответил бы вам тем же, положив свою первую монетку в один из оставшихся незанятым углов. Если углы так важны, то первые четыре хода должны быть сделаны именно в углы, но тогда каждый из вас будет контролировать по два угла и никто не получит преимущества. И что тогда? Снова ваш ход, можно ли говорить о каких-то существенных изменениях?

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

Стоп! Есть только одно исключение – ход, который ваш оппонент не сможет дублировать. Этот ход – положить вашу первую монетку точно в центр стола. Хотя в этой игре и нет «центральной клетки», есть уникальная позиция в центре стола – как только вы положили туда монету, никто другой ее уже не сможет занять.

Это еще не значит, что ход в центр стола – это хороший ход, но это уникальный первый ход, единственный ход в этой игре, когда игрок имеет возможность сделать его так, чтобы второй игрок не смог этот ход копировать.

Запомните эту мысль…

Что бы вы ни делали, другой игрок может класть свои монетки почти где угодно в начальной стадии игры. Поэтому, если у вас есть хорошая стратегия, которая также должна быть и простой стратегией, она должна быть основана на не требующих особенных раздумий парирующих ходах, которые позволят вам легко нейтрализовать любой ход противника.

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

Вы всегда сможете так поступать, так как вы просто дублируете последний ход вашего оппонента (если стол симметричный). В конце концов именно вашему оппоненту не удастся положить еще одну монету на стол так, чтобы он не прикасалась ни к одной из тех, которые уже лежат на столе.

Британский эксперт по головоломкам Генри И. Дьюдени вызвал при помощи этой игры ажиотаж в своем клубе в Лондоне (там они выкладывали на стол сигары). Игра описана в опубликованной в 1917 году книге Дьюдени «Математические развлечения» (Amusements in Mathematics). Версия Дьюдени с сигарами была особенно хитрой. Его уловка, которая всегда приносила ему выигрыш, была такой: он ставил сигару в самый центр стола вертикально. Следующие сигары можно было также ставить на стол вертикально или класть их на стол – это было безразлично, поскольку Дьюдени всегда мог отвечать противнику симметричным ходом. Американский соперник Дьюдени Сэм Ллойд использовал его идею, творчески ее развив: он использовал в игре куриные яйца. Чтобы яйцо могло стоять, нужно сделать небольшую вмятину на тупом конце яйца.

? Пять пиратов на острове должны разделить между собой сотню золотых монет…

Насколько нам известно, у пиратов равные права на монеты. Простейший план – поделить монеты поровну на пять частей. Тогда каждый получит по двадцать монет. Что плохого в таком решении?

В общем ничего, за исключением того, что вас могут убить. Вы предложите такое решение, а другие четыре пирата могут подумать, что двадцать монет – это хорошее решение, но двадцать пять монет – еще лучше. Именно столько они и получат, если проголосуют против вашего плана и убьют вас. Потом они снова начнут делить ту же сотню монет, но пиратов теперь будет только четверо.

Вы можете до посинения спорить, утверждая, что поделить добычу поровну – это самый честный план, но в условии головоломки ничего не говорится о том, что пираты – люди честные. Честность – это обычно не самое нужное пиратам качество. Причем отвергнуто будет не только первое предложение поделить все поровну: то же случится и со следующими подобными предложениями. Ведь лучше делить добычу на троих, чем на четверых? А на двоих лучше, чем на троих? Вам понятно, к чему это все приведет?

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

Эта головоломка – еще одно упражнение в рекурсивных рассуждениях. Чтобы найти решение, нужно понять, что ситуацию с n пиратов можно анализировать на основе ситуации с n – 1 пиратов и т. д., пока вы не доберетесь до «базовой ситуации», решение в которой будет абсолютно ясным.

Базовая ситуация – это один выживший пират. Очевидно, что единственный пират предложит отдать ему все монеты. Ход сделан!

А что если пиратов двое? Старшему из них придется предложить, как делить добычу. В условии головоломки говорится, что предложение принимается, если «по крайней мере половина пиратов» за него проголосует. Это значит, что достаточно одного голоса старшего пирата, чтобы предложение было принято. Следовательно, если пиратов всего двое, то старшему из них бояться нечего, и он может не беспокоиться о том, что думает его товарищ. Будучи жадным негодяем, старший пират предложит отдать все сто монет ему. Результаты голосования будут такими: один голос «за» и один «против» – это значит, что предложение будет принято.

Может показаться, что старший пират всегда получит то, чего он хочет. Не совсем так. Представьте, что он решил воспользоваться тем же трюком, если пиратов трое. Давайте пронумеруем пиратов, начиная с самого младшего: № 1, № 2, № 3. План раздела добычи должен предложить номер 3. Если он предложит такой план: «Все достается мне, а вы, ребята, ничего не получите», то следующий пират в этой последовательности (№ 2) точно проголосует против подобного предложения. Пират № 2 знает, что он сам получит все, если останутся только два пирата после того, как № 3 будет убит. Решающим оказывается голос пирата № 1. Он ничего не получает, если проголосует за план пирата № 3, но также ничего не получит, если проголосует против, если останутся только два пирата. У него нет никаких причин, чтобы предпочесть один вариант другому.

Итак, если № 3 умен, как это предполагается в головоломках, он попытается получить поддержку пирата № 1. Нужно также учесть, что пират № 3 жадный, и он готов отдать другому пирату только необходимый минимум. Логичным предложением со стороны пирата № 3 будет дать № 1 одну золотую монету, № 2 – ничего, а ему самому – оставшиеся девяносто девять монет! Поскольку № 1 также рассуждаете логично, но поймет, что и эти жалкие гроши лучше, чем ничего, а ведь он ничего не получит, если пират № 3 будет убит. Пират № 1 проголосует за план раздела добычи (как и № 3, конечно), и это предложение будет принято двумя голосами против одного несмотря на все проклятия накачавшегося с горя ромом пирата № 2.