Задача о нарезке арбуза¶

Задача о нарезке арбуза — классическая математическая задача о максимальном числе частей, на которые можно разделить объёмное тело (например, арбуз) заданным числом плоских разрезов. При десяти разрезах плоскостью арбуз можно разделить максимум на 176 кусочков. Задача является трёхмерным обобщением плоской задачи о разрезании блина и связана с известной последовательностью чисел, которую в англоязычной литературе называют lazy caterer's sequence (в трёхмерном случае — cake numbers).

¶Общая постановка

Задача формулируется следующим образом: имеется выпуклое тело (арбуз, шар, блин) и плоскость, которой его можно резать. Требуется найти наибольшее число фрагментов, на которые удастся разделить тело за заданное число разрезов. Ключевое условие — каждый новый разрез должен пересекать все предыдущие разрезы таким образом, чтобы число новых порождаемых частей было максимальным.

Для плоской задачи (нарезка блина) ответ при $n$ разрезах задаётся формулой:

$$L(n) = \frac{n(n+1)}{2} + 1$$

При десяти разрезах блин можно разделить максимум на 56 частей. Последовательность начинается с чисел 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56.

¶Трёхмерный случай

Для объёмного тела ответ описывается формулой:

$$C(n) = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \binom{n}{3} = \frac{n^3 + 5n + 6}{6}$$

При $n = 10$:

$$C(10) = 1 + 10 + 45 + 120 = 176$$

Таким образом, десять плоских разрезов арбуза дают максимум 176 кусочков. Последовательность чисел для $n = 0, 1, 2, \dots$ выглядит так: 1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176.

¶Условия достижения максимума

Чтобы достичь максимума, разрезы должны удовлетворять нескольким условиям:

• ни одна из плоскостей не должна проходить через общую линию пересечения двух предыдущих плоскостей;
• ни одна из плоскостей не должна проходить через точку пересечения трёх предыдущих плоскостей;
• все плоскости должны попарно пересекаться, и ни одна пара не должна быть параллельной;
• никакие четыре плоскости не должны пересекаться в одной точке.

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

¶Вывод формулы

Формула $C(n)$ выводится индуктивно. Пусть $n-1$ плоскостей уже разрезали тело на $C(n-1)$ частей. Добавление $n$-й плоскости увеличивает число частей на число регионов, на которые эта плоскость сама разрезается пересечениями с предыдущими $n-1$ плоскостями. Это ровно плоская задача для $n-1$ разрезов, то есть $L(n-1) = \frac{(n-1)n}{2} + 1$. Отсюда:

$$C(n) = C(n-1) + \frac{n(n-1)}{2} + 1$$

При суммировании получается формула биномиальных коэффициентов.

¶Связь с комбинаторикой

Число $C(n)$ равно числу областей, на которые пространство разбивается $n$ плоскостями в общем положении. Это частный случай более общей задачи о разбиении пространства гиперплоскостями. В $d$-мерном пространстве максимальное число частей при $n$ разрезах равно:

$$\sum_{k=0}^{d} \binom{n}{k}$$

Для $d = 2$ (плоскость, задача о блине) и $d = 3$ (арбуз) получаются рассмотренные формулы.

¶Практические соображения

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

¶Интересные факты

• Задача о нарезке блина входит в число популярных математических головоломок и регулярно встречается в олимпиадных заданиях.
• Трёхмерный вариант формулируется именно через арбуз в англоязычной традиции («watermelon cutting problem»), хотя математически тело может быть любым выпуклым.
• Числа последовательности $C(n)$ растут кубически, что принципиально отличает их от квадратичного роста в плоской задаче.

¶Источники

• Болтянский В. Г., Иванов М. А., Ордынский А. С. «Задачи школьных математических олимпиад»
• Graham R. L., Knuth D. E., Patashnik O. «Concrete Mathematics»
• Сборники задач по комбинаторной геометрии