Симпсоны и их математические секреты

«В нашем ресторане не очень аккуратный шеф-повар; когда он готовит блины, они получаются разных размеров. Вот почему, когда я отношу блины клиенту, по пути к столику мне приходится переворачивать несколько верхних блинов (так, чтобы самые маленькие были наверху, а самые большие – внизу). Я повторяю это столько раз, сколько нужно (меняя количество переворачиваемых блинов). Если есть n блинов, чему равно максимальное количество переворотов (как функции n), которое мне придется сделать, чтобы расположить блины в правильном порядке?»

Другими словами, если Гомер отправится в Спрингфилдский муниципальный дом блинов, как показано в эпизоде «Запутанный мир Мардж Симпсон» (The Twisted World of Marge Simpson, сезон 8, эпизод 11; 1997 год), и официант принесет ему n блинов разных размеров, уложенных в случайном порядке, то сколько переворотов ему потребуется сделать в самом худшем случае, для того чтобы расположить блины правильно? Число переворотов блинов обозначается как P_n. Задача состоит в том, чтобы найти формулу определения числа P_n.

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

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

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

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

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

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

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

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