Книга Симпсоны и их математические секреты - Саймон Сингх

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

Несколько простых примеров могут пролить свет на эту задачу. Во-первых, чему равно число переворотов, если в наличии всего один блин? Ответ: нулю, поскольку этот блин не может лежать неправильно. Следовательно, P1 = 0.

Чему равно число переворотов в случае двух блинов? Тут может быть только два варианта: либо их уложили правильно, либо в обратном порядке. Определить худший случай не составит труда, причем потребуется всего один переворот, для того чтобы обеспечить правильное расположение блинов. Следовательно, P2 = 1.

Далее, чему равно число переворотов в случае трех блинов? Вычислить это немного труднее, так как существует шесть вариантов их исходного порядка. И в зависимости от него число переворотов, необходимое для расположения блинов в правильном порядке, составляет от ноля до трех в самом худшем случае. Следовательно, P3 = 3.

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

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

Из-за сложности выполнения всех перестановок и возможных стратегий переворачивания блинов даже очень мощным компьютерам до сих пор не удалось рассчитать число переворотов в случае двадцати блинов. Кроме того, даже три десятилетия спустя никто не смог отказаться от метода решения «в лоб» с помощью компьютера и найти красивое уравнение для определения числа переворотов блинов. На данный момент единственным достижением в решении этой задачи стало выведение формулы определения границ для числа переворотов блинов. В 1979 году было доказано, что верхняя граница для числа переворотов составляет (5n + 5)/3 переворотов. Это значит, что мы можем взять бессмысленно огромное количество блинов (скажем, тысячу) и точно знать, что число переворотов, необходимых для их укладки в порядке возрастания (или убывания) размера, будет меньше, чем:

Таким образом, учитывая, что выполнить треть переворота невозможно, меньше или равно 1668. Этот знаменитый результат, поскольку он был опубликован в работе Христоса Пападимитриу и Уильяма Гейтса, который нам больше известен как Билл Гейтс, основатель компании Microsoft, а эта работа считается его единственной научной публикацией.

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

В 1995 году Коэн написал работу по задаче о подгоревших блинах[37], в которой вычислил верхний и нижний пределы числа переворотов подгоревших блинов: от 3n/2 до 2n − 2. Если мы снова используем пример с 1000 блинов, но теперь уже подгоревших, то сможем определить, что число переворотов, необходимых для их укладки подгоревшей стороной вниз, составляет от 1500 до 1998.

Это именно то, что делает сценаристов «Симпсонов» уникальными. Они не только посещают математический клуб, но еще и читают научные лекции и пишут серьезные математические научные работы.

Дэвид Коэн вспомнил историю, которая показывает, как сценаристы порой поражаются сами себе, когда осознают уровень математических знаний своей команды: «Я написал работу о количестве переворотов блинов в соавторстве со своим научным руководителем Мануэлем Блюмом, известным специалистом в области компьютерных наук, и мы отправили ее в журнал Discrete Applied Mathematics. Впоследствии я бросил магистратуру ради написания сценариев для “Симпсонов”. После того как нашу работу приняли, прошел очень большой отрезок времени, прежде чем ее проверили и опубликовали. Таким образом, к моменту ее публикации я уже работал какое-то время в команде “Симпсонов”, и примерно в тот же период туда пришел Кен Килер. Когда в конце концов моя научная статья появилась в журнале, я пришел с ее копией на работу и сказал: “Послушайте, а у меня вышла статья в Discrete Applied Mathematics”. Это произвело впечатление на всех, кроме Кена Килера, который заявил: “Ну да, я тоже опубликовал статью в этом журнале пару месяцев назад”».

С ухмылкой на лице Коэн проворчал: «Вот так вот, я пишу сценарии для “Симпсонов” и даже не могу быть единственным сценаристом сериала, опубликовавшим работу в Discrete Applied Mathematics?»

Глава 10

Теорема страшилы

Как правило, Гомера не считают гигантом мысли; он скорее пользуется репутацией одного из обычных жителей Спрингфилда. В эпизоде «Гомер против восемнадцатой поправки» (Homer vs. the Eighteenth Amendment, сезон 8, эпизод 18; 1997 год) он поднимает тост, который отражает его простую философию жизни: «За алкоголь! Причину и решение всех жизненных проблем!»

Тем не менее время от времени сценаристы все же дают Гомеру оторваться, чтобы исследовать нердовскую сторону его характера. Мы уже видели это в эпизоде «Волшебник Вечнозеленой аллеи» 1998 года; кроме того, есть и несколько эпизодов, в которых Гомер демонстрирует, что может быть образцовым гиком. Например, самый авторитетный в мире научный журнал Nature похвалил его за комментарий, сделанный в эпизоде «Забастовка учителей» (The PTA Disbands, сезон 6, эпизод 21; 1995 год). Поймав дочь на попытке построить вечный двигатель, Гомер твердо ставит ее на место: «В этом доме все подчиняется законам термодинамики!»