Саймон Сингх - Симпсоны и их математические секреты
Первое заседание клуба состоялось в квартире Брунн в сентябре 2002 года. Вступительную лекцию под названием «Сюрреальные числа» прочитал Дж. Стюарт Бернс, который начал работу над докторской диссертацией по математике перед тем, как стать членом команды «Симпсонов». Коллеги Бренса тоже выступали в математическом клубе с лекциями по таким темам, как «Введение в теорию графов», «Случайный выбор задач в теории вероятностей» и т. д.
Хотя математический клуб представлял собой неформальное объединение друзей и коллег с общими интересами, представленные на его заседаниях лекции зачастую имели безупречную научную репутацию. Кен Килер, лекция которого называлась «Подразбиение квадрата», – один из самых одаренных в математическом плане сценаристов «Симпсонов». Он окончил Гарвардский университет с отличием, что было признанием его блестящего математического таланта, и получил диплом бакалавра в 1983 году. Затем Килер поступил в Стэнфордский университет, чтобы получить диплом магистра по электротехнике, после чего снова вернулся в Гарвард, где защитил докторскую диссертацию по теме «Представление карт и оптимальное кодирование для сегментации изображений» в области прикладной математики. После этого Килера приняли в AT&T Bell Laboratories в Нью-Джерси, на счету сотрудников которых было семь Нобелевских премий. Именно в этот период и пересеклись пути Кена Килера и Джеффа Уэстбрука. Оба работали в одной и той же сфере исследований и совместно написали работу под названием «Укороченное кодирование планарных графов и карт»[36]. Кроме того, Килер и Уэстбрук также были соавторами сценария научно-фантастического телесериала Star Trek: Deep Space Nine («Звездный путь: Глубокий космос 9»), в котором два комика развязали войну, оскорбив своими шутками каждого присутствовавшего в зале инопланетянина.
Численность членов математического клуба неуклонно росла. Иногда, для того чтобы вместить всех желающих, приходилось проводить заседания на улице, используя простыню в качестве экрана проектора. Больше всего членов клуба, порой около ста человек, приходили послушать лекции знаменитых математиков, таких как, например, доктор Рональд Грэм – главный научный сотрудник Калифорнийского института телекоммуникаций и информационных технологий (Cal-(IT)²). Кстати, Грэм написал более двух десятков работ в соавторстве с Палом Эрдешем, а также является главным популяризатором концепции чисел Эрдеша. Кстати, у Грэма есть еще один предмет для гордости – число Грэма – самое большое число из когда-либо использовавшихся в математическом доказательстве, которое он открыл в 1977 году. Чтобы получить представление о его истинном размере, возьмем такую величину, как планковский объем, которая является минимальной единицей объема в физике. Один атом водорода содержит 1073 таких объемов. Если бы цифры числа Грэма были записаны на ткани космоса таким образом, чтобы каждая цифра занимала один планковский объем, то всей видимой Вселенной оказалось бы недостаточно, чтобы вместить все цифры этого числа. Возможно, вам будет интересно узнать его последние десять цифр: … 2464195387.
Одну из самых запоминающихся лекций прочитал в математическом клубе Дэвид Коэн, создатель последней теоремы Гомера. Выступление Коэна было особенным потому, что он посвятил его научному исследованию, которое провел перед тем, как стать комедийным сценаристом. После окончания Гарвардского университета Коэн один год проработал в Гарвардской лаборатории робототехники, после чего поступил в Калифорнийский университет в Беркли для получения степени магистра компьютерных наук. Во время учебы в Беркли Коэн изучал так называемую задачу блинной сортировки – именно эта тема и легла в основу его лекции в математическом клубе.
Задачу блинной сортировки впервые сформулировал в 1975 году Джейкоб Гудман, геометр из Городского колледжа Нью-Йорка, известный под псевдонимом Гарри Двейтер (англ. Harry Dweighter, созвучно с harried waiter – «обеспокоенный официант»). Он писал:
«В нашем ресторане не очень аккуратный шеф-повар; когда он готовит блины, они получаются разных размеров. Вот почему, когда я отношу блины клиенту, по пути к столику мне приходится переворачивать несколько верхних блинов (так, чтобы самые маленькие были наверху, а самые большие – внизу). Я повторяю это столько раз, сколько нужно (меняя количество переворачиваемых блинов). Если есть n блинов, чему равно максимальное количество переворотов (как функции n), которое мне придется сделать, чтобы расположить блины в правильном порядке?»
Другими словами, если Гомер отправится в Спрингфилдский муниципальный дом блинов, как показано в эпизоде «Запутанный мир Мардж Симпсон» (The Twisted World of Marge Simpson, сезон 8, эпизод 11; 1997 год), и официант принесет ему n блинов разных размеров, уложенных в случайном порядке, то сколько переворотов ему потребуется сделать в самом худшем случае, для того чтобы расположить блины правильно? Число переворотов блинов обозначается как Pn. Задача состоит в том, чтобы найти формулу определения числа Pn.
Задача блинной сортировки сразу же привлекла внимание математиков по двум причинам. Во-первых, было похоже, что она позволит лучше понять способы решения задач по информатике, поскольку перегруппировка блинов имеет много общего с перегруппировкой данных. Во-вторых, эта головоломка казалась достаточно трудной, а математики просто обожают задачи, граничащие с невозможным.
Несколько простых примеров могут пролить свет на эту задачу. Во-первых, чему равно число переворотов, если в наличии всего один блин? Ответ: нулю, поскольку этот блин не может лежать неправильно. Следовательно, P1 = 0.
Чему равно число переворотов в случае двух блинов? Тут может быть только два варианта: либо их уложили правильно, либо в обратном порядке. Определить худший случай не составит труда, причем потребуется всего один переворот, для того чтобы обеспечить правильное расположение блинов. Следовательно, P2 = 1.
Далее, чему равно число переворотов в случае трех блинов? Вычислить это немного труднее, так как существует шесть вариантов их исходного порядка. И в зависимости от него число переворотов, необходимое для расположения блинов в правильном порядке, составляет от ноля до трех в самом худшем случае. Следовательно, P3 = 3.
В большинстве случаев вы сами можете уложить блины в нужном порядке с помощью приемлемого количества переворотов. Однако порой процесс перестановки неочевиден, поэтому ниже показана серия из трех переворотов. В каждом ряду отображен процесс одного переворота, а именно куда следует вставить лопатку и каким будет порядок укладки блинов в результате переворота.
По мере увеличения стопки блинов задача усложняется в связи с ростом количества вариантов исходного порядка расположения блинов, а также числа возможных способов переворачивания. Более того, создается впечатление, что в последовательности чисел, соответствующих количеству переворотов блинов, нет никакой закономерности:
Из-за сложности выполнения всех перестановок и возможных стратегий переворачивания блинов даже очень мощным компьютерам до сих пор не удалось рассчитать число переворотов в случае двадцати блинов. Кроме того, даже три десятилетия спустя никто не смог отказаться от метода решения «в лоб» с помощью компьютера и найти красивое уравнение для определения числа переворотов блинов. На данный момент единственным достижением в решении этой задачи стало выведение формулы определения границ для числа переворотов блинов. В 1979 году было доказано, что верхняя граница для числа переворотов составляет (5n + 5)/3 переворотов. Это значит, что мы можем взять бессмысленно огромное количество блинов (скажем, тысячу) и точно знать, что число переворотов, необходимых для их укладки в порядке возрастания (или убывания) размера, будет меньше, чем:
Таким образом, учитывая, что выполнить треть переворота невозможно, меньше или равно 1668. Этот знаменитый результат, поскольку он был опубликован в работе Христоса Пападимитриу и Уильяма Гейтса, который нам больше известен как Билл Гейтс, основатель компании Microsoft, а эта работа считается его единственной научной публикацией.
В работе Гейтса, написанной им в период учебы в Гарвардском университете, упоминается также более сложный вариант этой задачи. В задаче о подгоревших блинах фигурируют блины, подгоревшие с одной стороны, которые необходимо уложить в правильном порядке, переворачивая так, чтобы подгоревшая сторона оказывалась внизу. Именно эту задачу решил Дэвид Коэн во время учебы в Беркли.
