Задача блинной группировки

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

Задача в сериале не формулируется, в чем можно убедиться здесь

Тем не менее, как утверждает Сингх, сценаристы о ней думали. Вот как она звучит:

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

Замените «блины» на «данные» и тогда станет понятно, какая практическая польза может быть от решения.

Количество переворотов зависит от первоначального расположения блинов. Если блина всего три, то вариантов шесть, а необходимое количество переворотов в худшем случае составит три.

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

Но не все так безнадежно. В 1979 году было доказано, что число переворотов точно не может быть больше (5n + 5)/3.

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