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

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

Считается, что задача о секретаре впервые была опубликована (без непосредственного упоминания секретарей) в февральском номере журнала Scientific American в 1960 году Мартином Гарднером в качестве одной из головоломок в его популярной колонке о занимательной математике. Однако само происхождение задачи остается загадкой. Наше собственное расследование с нуля привело нас к некоторой гипотезе еще до того, как оно неожиданно превратилось для нас в детективную работу в прямом смысле слова. Мы отправились в Стэнфорд, чтобы в архивах работ Гарднера найти его переписку середины прошлого века. Чтение писем немного напоминает подслушивание чужого телефонного разговора: вы слышите только одну сторону диалога, а ответ можете лишь предположить. В нашем случае у нас были только ответы на вопросы, которыми, очевидно, задавался сам Гарднер более 50 лет назад, исследуя историю происхождения задач. Чем больше мы читали, тем более запутанной и неясной казалась нам эта история. Гарвардский математик Фредерик Мостеллер вспомнил, что слышал об этой задаче в 1955 году от своего коллеги Эндрю Глизона, который, в свою очередь, слышал о ней от кого-то еще. Лео Мозер из Альбертского университета рассказывал в своем письме, что читал о головоломке в «неких записях» Р. И. Гаскелла из компании Boeing, который приписывал авторство задачи своему коллеге. Роджер Пинкхам из Ратгерского университета писал, что впервые услышал о головоломке в 1955 году от математика по фамилии Шонфильд из Университета Дьюка, а тот, по его убеждению, сам впервые услышал о задаче от кого-то из Мичигана. Этот «кто-то из Мичигана», с большой вероятностью, носил имя Меррил Флад. И хотя за пределами мира математики его имя мало кому известно, влияние Флада на развитие компьютерной науки нельзя не отметить. Именно он обратил внимание на задачу о коммивояжере (которую мы обсудим более подробно в главе 8), изобрел математическую игру «Два бандита» (которая будет описана в главе 11) и даже, весьма вероятно, ввел термин «программное обеспечение». По его же собственным словам, Флад приступил к изучению вопроса в 1949-м и в 1958 году стал автором своего первого известного открытия – правила 37 %. Хотя он и отдает пальму первенства в этом вопросе другим математикам.

Достаточно будет отметить, что вне зависимости от своего происхождения задача о секретаре оказалась едва ли не идеальной математической загадкой: ее легко объяснить, очень сложно решить, решение ее чрезвычайно лаконично, а выводы крайне занимательны. В результате она передавалась из уст в уста в математических кругах в 50-е годы, распространяясь со скоростью лесного пожара, и только благодаря Гарднеру и его колонке в 1960 году захватила воображение широкой общественности. К 80-м задача и различные ее вариации столько раз подвергались анализу, что ее стали обсуждать в газетах как подраздел самой себя.

А что до секретарей, довольно умилительно наблюдать, как каждая культура накладывает свой особый антропологический отпечаток на формальные системы. К примеру, при мысли о шахматах нам представляется средневековая Европа, хотя на самом деле появились шахматы в VIII веке в Индии. Они были достаточно грубо «европеизированы» в XV веке, когда «шахи» были переименованы в «королей», «визири» – в «королев», а «слоны» стали «офицерами».

Аналогичным образом менялись и задачи об оптимальной остановке, отражая насущные проблемы и переживания каждого поколения. В XIX веке типичными ситуациями для таких задач были барочные лотереи или выбор подходящего поклонника для дамы; в начале XX века – поиск лучшего отеля для автопутешественника и выбор подходящей спутницы для мужчины; в середине XX века, во время расцвета офисной рутины и доминирования мужчин, – подбор лучшей секретарши для руководителя-мужчины. Впервые название задачи о секретаре именно в такой формулировке было упомянуто в газете в 1964 году, позднее оно закрепилось окончательно.