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

Задачу блинной сортировки впервые сформулировал в 1975 году Джейкоб Гудман, геометр из Городского колледжа Нью-Йорка, известный под псевдонимом Гарри Двейтер (англ. Harry Dweighter, созвучно с harried waiter – «обеспокоенный официант»). Он писал:

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

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

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

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

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

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

В большинстве случаев вы сами можете уложить блины в нужном порядке с помощью приемлемого количества переворотов.