Вот настоящая математическая загадка – простая задача, решение которой пока ускользает от ученых не хуже, чем преступный гений Могиарти.

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

Приведем пример с четырьмя блинами. Для их упорядочивания требуется три переворота.

Вот несколько вопросов для вас.

1. Любую ли стопку из четырех блинов можно упорядочить не более чем за три переворачивания?

2. Если нет, то каково наименьшее число переворачиваний, при помощи которых можно упорядочить любую стопку из четырех блинов?

3. Определите для n-го блина число Pn – наименьшее число переворачиваний, при помощи которых можно упорядочить любую стопку из n блинов. Докажите, что Pn всегда конечно. То есть что любую стопку блинов можно упорядочить при помощи конечного числа переворачиваний.

4. Найдите P_n для n = 1, 2, 3, 4, 5. Я остановился на n = 5, потому что здесь мы уже имеем 120 различных вариантов стопки, все из которых нужно рассмотреть, а это, говоря откровенно, уйма работы.