Как вы отыщете нужную вам книгу в большой библиотеке?

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

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

В большинстве библиотек книги размещают в соответствии с их номерами в каталоге. Две наиболее популярные системы книжных каталогов в США — десятичная система Дьюи и система Библиотеки Конгресса США — отличаются друг от друга, и их нельзя считать универсальными. В библиотеках раритетных книг их обычно размещают в соответствии с датой первой публикации. Есть и просто странные системы. Например, в библиотеке института Warburg книги на разные темы специально перемешаны на полках, чтобы вызывать неожиданные ассоциации, помогающие развитию междисциплинарных исследований. Основатель этого института Эйби Варбург придумал и внедрил эту систему еще до того, как был помещен в сумасшедший дом для лечения.

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

Каждый раз, просматривая книги, обращайте внимание не только на их тематику и названия, но и на систему размещения на полке. Можно ли утверждать, что книги, близкие по тематике, стоят рядом? (Скорее всего так и есть, и тогда это очень важная и полезная информация.) Или они расставлены в случайном порядке? (Будем надеяться, что это не так, но нужно проверить.) Расставлены ли книги по алфавиту (по авторам, по названию, по тематике) или это полка для книг крупного формата, которые стоят здесь, так как не поместились на обычных полках? Везде ли, где вы проверили, система размещения книг одинакова или она варьируется?

Допустим, книга, которую вы ищете, это The Seattle Junior League Microwave Cookbook («Сборник кулинарных рецептов для микроволновой печки для начинающих кулинаров Сиэтла»). Если вы наткнетесь на полку, где размещаются кулинарные книги, — вам повезло. Нужная вам книга где-то поблизости. Если в библиотеке не очень много кулинарных книг, вы можете не составлять план и просто просмотреть полки с кулинарными книгами, но если таких книг очень много, вам все равно понадобится план. Имеет смысл изменить план выборочных поисков, используя более крупный (то есть подробный) масштаб и поместив в центр плана уже обнаруженную вами полку книг с кулинарными рецептами. Возможно, вы обнаружите разделы с книгами рецептов американской кухни, раздел с кулинарными рецептами для микроволновок, раздел с кулинарными рецептами северо-запада тихоокеанского побережья США или рецептами для благотворительных кухонь для бездомных.

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

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

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

Вот такой примерно ответ ожидают интервьюеры Microsoft. Более краткий ответ предлагается на веб-сайте acetheinterview.com: «Я выйду из библиотеки, отыщу человека, придумавшего этот вопрос, и дам ему оплеуху».[149]

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

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

Нет проблем с оценкой расходов фирмы. IRS обычно достаточно хорошо представляет, сколько фирма определенного размера в той или иной отрасли бизнеса может потратить на канцелярские принадлежности и оплату телефонных счетов, на аренду офиса и зарплаты работников, на рекламу и свой сайт в Интернете. Если есть какие-то сомнения, их легко разрешить во время визита в фирму — сразу станет ясно, верна ли информация о количестве сотрудников фирмы и арендной плате. Труднее проверить информацию о доходах. Фирма по предоставлению услуг нянь находит желающих получить такую работу и направляет их в семьи, получая плату за услуги нянь от родителей детей, за которыми няни присматривают, и выплачивая няням зарплату. После этого всю ответственность за уплату налогов несут семьи-наниматели и сами няни. Семьи обязаны заполнить форму W-2 и уплатить налог в фонд страхования по безработице.

Это дает один из возможных способов проверить работу фирмы, предоставляющую услуги нянь, при помощи данных, уже имеющихся в распоряжении IRS. Для этого, пользуясь налоговыми формами W-2 и 1040, можно составить список нянь, работающих в данном районе. Сравнив эти данные за прошлый год по тем же формам W-2 и 1040, IRS может определить, сколько новых нянь появилось за прошедший год.

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

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

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

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

У вас восемь бильярдных шаров…

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

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

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

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

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

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

Эта головоломка хорошо известна во всем мире. Она была, например, опубликована в 1956 году в книге Бориса Кордемского «Математическая смекалка», которая была бестселлером в Советском Союзе времен «холодной войны».[150]

Если у вас пять баночек с таблетками…

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

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

Это значит, что вам нужно одновременно взвешивать таблетки не из одной баночки, а из нескольких. Рассмотрим простейший случай: вы взвешиваете пять таблеток, по одной из каждой баночки. Тогда итоговый вес обязательно окажется 10+ 10 + 10+ 10 + 9 = 49 граммов. Проблема в том, что это можно узнать и без всякого взвешивания. Это никак не поможет вам узнать, из какой баночки вы взяли дефектную 9-граммовую таблетку.

Вам нужно придумать такую ситуацию, в которой вес таблеток был бы информативным. Одно из решений—пронумеровать баночки №1, №2, №3, №4, №5. Потом вы кладете на весы одну таблетку из баночки №1, две — из №2, три из №3, четыре из №4 и пять из №5. Вы взвешиваете одновременно все эти таблетки. Если бы все таблетки были нормального веса, то результат был бы 10 + 20 + 30 + 40 + 50 = 150 граммов. На самом деле вес будет меньше, причем на количество граммов, которое соответствует номеру баночки с испорченными таблетками. Например, если общий вес будет 146 граммов (на 4 грамма меньше), это значит, что более легкие дефектные таблетки — в баночке №4.

Альтернативное решение позволяет определить дефектную бутылку, взвесив меньше таблеток: 1 + 2 + 3 + 4 таблеток из первых четырех баночек. Тогда если вес окажется меньше 100 граммов, то количество граммов, которого не хватает до 100, укажет вам номер дефектной баночки. Если же вес будет ровно 100 граммов, это означает, что дефектные таблетки в пятой баночке.

После того, как вы найдете правильный ответ, вы можете спросить интервьюера о том, для кого предназначаются эти таблетки. Хороший ответ на этот вопрос — «для лошади». 10-граммовая таблетка весит в тридцать раз больше, чем обычная (325 миллиграммов) таблетка аспирина.

Эта головоломка (правда, речь шла о взвешивании монет) упоминалась Мартином Гарднером в его колонке в журнале Scientific American в середине 1950-х. Гарднер описывал ее как «новую и элегантную вариацию» задач о взвешивании, «популярных в последние годы».[151]

Три муравья находятся в трех углах равностороннего треугольника…

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

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

Четыре собаки находятся в разных углах большого квадрата…

Чтобы упростить решение задачи, предположим, что длина стороны квадрата 1 миля, а собаки — это гончие, выведенные генетиками, которые бегут со скоростью ровно одна миля в минуту. Представьте себе, что вы блоха, которая едет на спине собаки номер 1. У вас есть крошечный радар, который позволяет вам точно измерить скорость движения других объектов относительно вашей системы отсчета (ею служит в данном случае собака номер 1, в шерсть который вы вцепились пятью вашими лапками, а в шестой вы держите радар). Собака 1 преследует собаку 2, которая преследует собаку 3, которая преследует собаку 4, которая, в свою очередь, преследует собаку 1. В начале погони вы направляете радар на собаку 4 (которая гонится за вами). Радар вам сообщает, что собака 4 приближается к вам со скоростью 1 миля в минуту.

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

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

Не играет никакой роли, что ваша система отсчета (то есть собака) сама движется относительно других собак. Эта система отсчета не хуже любой другой (если интервьюеры станут к вам приставать по этому поводу, отвечайте им, что так сказал Эйнштейн). Единственное, что играет роль, — собака 4 приближается к вам с постоянной скоростью. Поскольку в начале погони собака 4 находилась от вас на расстоянии одной мили и приближалась к вам с постоянной скоростью 1 миля в минуту, она непременно столкнется с вами через одну минуту. Блохи-наездники на других собаках, несомненно, придут к такому же выводу. Все собаки столкнутся друг с другом через минуту после старта.

Где это произойдет? Собаки движутся по абсолютно симметричным траекториям. Было бы странно, если бы они при этом отклонились на «две трамвайные остановки» к востоку или западу. Нет никакой силы, которая бы подталкивала их к востоку или западу. Что бы ни происходило, симметрия исходной ситуации должна сохраниться. Если уж собакам суждено догнать друг друга — это произойдет точно в середине квадрата.

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

Эту задачу также в 1950-х годах упоминал Мартин Гарднер.[152]

Поезд отправляется из Лос-Анджелеса в Нью-Йорк с постоянной скоростью…

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

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

В тот самый миг, когда птица долетит до Западного поезда, она поворачивает и летит в обратную сторону. Теперь она уже летит впереди Западного поезда на запад навстречу Восточному. И снова птица первая встретится со встречным поездом. Она снова поворачивает обратно, и начинается новый цикл. Единственная разница в том, что с каждым новым циклом поезда оказываются все ближе и ближе друг к другу. Неважно, насколько близко, потому что птица каждый раз успевает улететь в обратную сторону еще до того, как произойдет столкновение. Это значит, что птица снует туда-сюда бесчисленное множество раз.

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

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

Вообще-то можно не беспокоиться о бесконечных рядах. Два поезда сближаются с относительной скоростью 35 миль в час (15 + 20 миль в час). Допустим, расстояние между Нью-Йорком и Лос-Анджелесом — 3500 миль. Тогда столкновение поездов произойдет через 3500/35, или 100 часов.

Все это время птица будет в полете, летая между поездами с постоянной скоростью 25 миль в час. Хотя направление полета и меняется, она тем не менее постоянно летит именно с этой скоростью. Таким образом, летая со скоростью 25 миль в час в течение ста часов, птица пролетит 25 х 100 = 2500 миль. Или, если D — это реальное расстояние между Лос-Анджелесом и Нью-Йорком, то столкновение между поездами произойдет через D/35 часов, а птица за это время пролетит 25D / 35, или 5D / 7 миль.

Рассказывают, что кто-то задал один из вариантов этой задачи математику Джону фон Нейману (1903-1957). Тот так быстро дал ответ, что его знакомый сказал: «Ну, ты, наверное, знал, в чем здесь трюк».

«Какой трюк? — спросил Фон Нейман. — Я просто вычислил сумму бесконечного ряда».

У вас 26 констант…

Вы читаете английские тексты слева направо, поэтому, допустим, что вы попали в эту ловушку и начали анализировать выражение слева. Что такое константа X?

X — это двадцать четвертая буква английского алфавита, равная 24, возведенным в степень, значение которой равно значению предыдущей константы W. Поскольку W — это двадцать три в степени U, которая 22 в степени Т, которое 21 в степени… X

Все это значит, что X — это 24, возведенные в степень 23 в степени 22 в степени 21… и так далее, до 3 в степени 2 в степени 1. То есть это 23-ступенчатые экспоненты.

X — это очень большое число.

Поисковый интернет-портал Google (произносится Гугл) получил свое название от числа, название которого, правда, пишется чуть иначе — googol (гугол), значение которого можно записать как единицу со ста нулями. Есть еще большее число, названное googolplex (гуголплекс)—это единица, за которой следует гугол нулей. Ни гугол, ни гуголплекс не имеют никакого практического применения за исключением иллюстрации того факта, что существуют абсурдные огромные числа. В наблюдаемой вселенной нет никаких объектов, количество которых составляло бы гугол. А гуголплекс — это такое огромное число, что его даже не записать. Поскольку количество нулей в этом числе — гугол, а даже количество атомов или кварков во вселенной меньше, вам никогда не написать это число на бумаге, сколько бы у вас ни было бумаги и каким бы мелким почерком вы ни писали.

Но даже гуголплекс — это маленькое число, если сравнить его с числом X из головоломки Microsoft. Корпорация Intel еще не изготовила достаточно микропроцессоров, чтобы рассчитать значение X. Даже если закон Мура будет выполняться до конца времен и каждые пять лет будут появляться новые Супер-Пентиумы и вы заполните всю вселенную этими процессорами, вы все равно не сможете рассчитать невообразимо огромное значение X.

Тот факт, что интервьюер просит вас рассчитать точное количественное значение выражения, в котором таких X множество, должно подсказать вам, что здесь есть какой-то трюк.

Правильный ответ — ноль. Среди 26 сомножителей должен быть один со значением (X — X) — а это, конечно, ноль. Неважно, чему равны все остальные сомножители — что бы вы ни умножили на ноль, результатом все равно будет ноль.

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

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