В большинстве случаев вы сами можете уложить блины в нужном порядке с помощью приемлемого количества переворотов. Однако порой процесс перестановки неочевиден, поэтому ниже показана серия из трех переворотов. В каждом ряду отображен процесс одного переворота, а именно куда следует вставить лопатку и каким будет порядок укладки блинов в результате переворота.
По мере увеличения стопки блинов задача усложняется в связи с ростом количества вариантов исходного порядка расположения блинов, а также числа возможных способов переворачивания. Более того, создается впечатление, что в последовательности чисел, соответствующих количеству переворотов блинов, нет никакой закономерности:
Из-за сложности выполнения всех перестановок и возможных стратегий переворачивания блинов даже очень мощным компьютерам до сих пор не удалось рассчитать число переворотов в случае двадцати блинов. Кроме того, даже три десятилетия спустя никто не смог отказаться от метода решения «в лоб» с помощью компьютера и найти красивое уравнение для определения числа переворотов блинов. На данный момент единственным достижением в решении этой задачи стало выведение формулы определения границ для числа переворотов блинов. В 1979 году было доказано, что верхняя граница для числа переворотов составляет (5n + 5)/3 переворотов. Это значит, что мы можем взять бессмысленно огромное количество блинов (скажем, тысячу) и точно знать, что число переворотов, необходимых для их укладки в порядке возрастания (или убывания) размера, будет меньше, чем:
Таким образом, учитывая, что выполнить треть переворота невозможно, меньше или равно 1668. Этот знаменитый результат, поскольку он был опубликован в работе Христоса Пападимитриу и Уильяма Гейтса, который нам больше известен как Билл Гейтс, основатель компании Microsoft, а эта работа считается его единственной научной публикацией.
В работе Гейтса, написанной им в период учебы в Гарвардском университете, упоминается также более сложный вариант этой задачи. В задаче о подгоревших блинах фигурируют блины, подгоревшие с одной стороны, которые необходимо уложить в правильном порядке, переворачивая так, чтобы подгоревшая сторона оказывалась внизу. Именно эту задачу решил Дэвид Коэн во время учебы в Беркли.
В 1995 году Коэн написал работу по задаче о подгоревших блинах, в которой вычислил верхний и нижний пределы числа переворотов подгоревших блинов: от 3n/2 до 2n − 2. Если мы снова используем пример с 1000 блинов, но теперь уже подгоревших, то сможем определить, что число переворотов, необходимых для их укладки подгоревшей стороной вниз, составляет от 1500 до 1998.
Это именно то, что делает сценаристов «Симпсонов» уникальными. Они не только посещают математический клуб, но еще и читают научные лекции и пишут серьезные математические научные работы.
Дэвид Коэн вспомнил историю, которая показывает, как сценаристы порой поражаются сами себе, когда осознают уровень математических знаний своей команды: «Я написал работу о количестве переворотов блинов в соавторстве со своим научным руководителем Мануэлем Блюмом, известным специалистом в области компьютерных наук, и мы отправили ее в журнал Discrete Applied Mathematics. Впоследствии я бросил магистратуру ради написания сценариев для “Симпсонов”. После того как нашу работу приняли, прошел очень большой отрезок времени, прежде чем ее проверили и опубликовали. |