Задача Мондриана

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

а) В нашем разбиении могут использоваться прямоугольники, обе стороны которых не больше 5, а площадь не превосходит 25. Несложно перечислить все такие прямоугольники:
    один прямоугольник площади 1: 1×1,
    один прямоугольник площади 2: 2×1,
    один прямоугольник площади 3: 3×1,
    два прямоугольника площади 4: 2×2 и 4×1,
    один прямоугольник площади 5: 5×1,
    один прямоугольник площади 6: 3×2,
    один прямоугольник площади 8: 4×2,
    один прямоугольник площади 9: 3×3,
    один прямоугольник площади 10: 5×2,
    один прямоугольник площади 12: 4×3,
    один прямоугольник площади 15: 5×3,
    один прямоугольник площади 16: 4×4,
    один прямоугольник площади 20: 5×4,
    один прямоугольник площади 25: 5×5.

Более-менее ясно, что большие прямоугольники нам тут вряд ли понадобятся.

Теперь подумаем, сколько из них мы можем попытаться использовать. Этот вопрос, как ни странно, вообще не имеет отношения к геометрии — это чисто комбинаторная и/или теоретико-числовая задача: на какое наибольшее число различных положительных слагаемых можно разбить данное число (в нашем случае — 25)? Заметим, что сумма первых шести натуральных чисел \(1+2+3+4+5+6=21<25\), а сумма первых семи натуральных чисел \(1+2+3+4+5+6+7=28>25\). Это значит, что семь прямоугольников использовать точно не получится — даже в «минимальном» варианте их суммарная площадь больше, чем 25. Значит, надо пробовать обойтись шестью.

Как представить 25 в виде сумме шести различных слагаемых и сколькими способами это можно сделать? Проще всего взять сумму \(1+2+3+4+5+6\) и немного «подкрутить» ее так, чтобы в результате получилось нужное значение. Всего возможно пять вариантов:

Почему нет других способов? Это можно доказать перебором или, например, воспользоваться таблицей значений для функции \(Q(n,\,k)\), которая, собственно, и выдает число способов разбить число \(n\) на \(k\) различных слагаемых. Эта функция есть в Онлайн-энциклопедии целочисленных последовательностей (OEIS), см. запись A008289. Нам нужно значение \(Q(25, 6)\), оно равно 5.

Сразу видно, что две из пяти сумм не годятся — в них входит число 7, которое не может быть площадью прямоугольника разбиения. Оставшиеся три суммы можно реализовать как разбиения квадрата площадью 25 (рис. 2).

Рис. 2.

В первоначальной формулировке пункта а) по недосмотру автора требовалось, чтобы среди прямоугольников разрезания не было одинаковых (вместо одинаковых по площади). В таком варианте задача допускает разрезание квадрата 5×5 на семь частей. Это разрезание показано на рис. 3.

Рис. 3.

б) Ясно, что из показанных на рис. 2 трех разбиений наименьшее качество у третьего, оно равно \(8-1=7\). У разбиения на рис. 3 качество равно \(6-1=5\). Можно ли добиться лучшего?

Оказывается, что можно. И основная идея здесь — не искать как можно более «мелкое» разбиение, а пытаться сделать так, чтобы самый большой и самый маленький прямоугольник были как можно ближе друг к другу по площади. Для этого надо (возможно, вопреки интуиции) стараться сделать самый маленький из прямоугольников как можно больше. Немного поперебирав варианты, можно найти разбиение, показанное на рис. 4. В нем всего три части, площади которых равны 6, 9 и 10, поэтому качество этого разбиения, а с ним — и квадрата 5×5, равно 4. Лучшего добиться невозможно.

Рис. 4.

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

В пункте а) нашей задачи довольно быстро стало понятно, что на самом деле речь идет о поиске разбиений числа 25 на различные слагаемые. Это частная форма более общего вопроса: сколькими способами можно представить данное число N в виде суммы нескольких слагаемых? Иными словами, сколько существует разбиений данного числа N? Число разбиений обычно обозначают \(p(N)\), эта функция (которая по натуральному числу выдает количество его разбиений, при этом разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми) играет очень важную роль в комбинаторике.

Интересно, что эта тема изучается математиками уже несколько столетий, но найти хотя бы какую-то замкнутую формулу для \(p(N)\) никому не удалось. Лучшее, что есть на сегодняшний день — это рекуррентная формула (надо сказать, не слишком изящная) и производящая функция \(\sum\limits_{n=0}^\infty p(n)x^n=\prod\limits_{k=1}^\infty \frac{1}{1-x^k}\). Эту знаменитую формулу открыл великий Леонард Эйлер в 1740 году. Суть производящей функции для последовательности в том, что, с одной стороны, мы рассматриваем элементы последовательности как коэффициенты при степенях переменной \(x\) в формальном степенном ряду, а с другой стороны часто (для важных последовательностей) оказывается так, что этот же ряд, благодаря каким-либо дополнительным соображениям, можно записать в более компактном виде. Такая трансформация позволяет в некоторых случаях получать удобные формулы для вычисления последующих элементов последовательности. Эйлером была доказана и так называемая пентагональная теорема (см. Pentagonal number theorem), дающая выражения для произведения (точнее, для обратной величины) в правой части приведенного выше равенства в виде ряда.

Если же говорить о нашем частном случае — о разбиениях на различные слагаемые, — то и здесь Эйлеру принадлежит важный результат. Оказывается, количество разбиений данного числа N на различные слагаемые равно числу разбиений N на нечетные слагаемые. Доказывать это можно разными способами и, пожалуй, самое короткое доказательство задействует все те же производящие функции. Но проще всего рассуждать следующим образом. Рассмотрим какое-либо разбиение числа N на нечетные слагаемые: \(N=N_1\cdot1+N_3\cdot3+N_5\cdot5+\ldots\). Здесь имеются коэффициенты \(N_i\), поскольку нечетным слагаемым разрешено повторяться (какие-то из них, впрочем, могут быть нулевыми). Каждый коэффициент \(N_i\) можно разложить по степеням двойки (по сути, это перевод числа в двоичную запись): \(N_i=2^{a_i}+2^{b_i}+2^{c_i}+\ldots\), где все показатели степеней различны. Но если подставить эти разложения в разложение \(N\) на нечетные слагаемые, то получим разложение, в котором все слагаемые, очевидно, различны: \(N=2^{a_1}+2^{b_1}+2^{c_1}+\ldots+2^{a_3}\cdot3+2^{b_3}\cdot3+\ldots+2^{a_5}\cdot5+\ldots\). Такое соответствие между разбиениями взаимно-однозначное (это, конечно, надо еще аккуратно доказать).

В качестве дальнейшего знакомства с этой очень богатой и интересной темой рекомендую статью В. Горина «Что можно сложить из кубиков?» («Квант» №3, 2012).

«Задачей Мондриана» (Mondrian Art Problem) традиционно называют вопрос из пункта б) нашей задачи. Хотя, судя по нынешнему состоянию дел, правильнее называть ее головоломкой чем задачей. Дело в том, что никаких общих методов для решения пока не придумано, — для поиска оптимальных решений нет ничего лучше, чем (оптимизированный) перебор размеров и вариантов расположения прямоугольников в квадрате.

Тем не менее, кое-какие оценки на качество квадрата сделать можно. Так, если длина стороны квадрата нечетна, то качество заведомо не больше длины стороны. Действительно, такой квадрат можно разрезать на два прямоугольника, у которых длинная сторона равна стороне квадрата, а короткие стороны отличаются на 1 (рис. 5). Разница площадей в этом случае равна длине стороны квадрата. Для квадрата с четной длиной стороны такой наивный подход дает оценку, равную удвоенной длине стороны квадрата, что, конечно, не слишком информативно. Более продвинутые оценки даны в статье New results for the Mondrian art problem.

Рис. 5.

Алгоритм поиска наиболее качественных разрезаний описан в статье Further Insight into the Mondrian Art Problem. Там же приведены эмпирически наиболее качественные разрезания для квадратов со стороной вплоть до 32. Описанный в статье алгоритм — это несколько оптимизированная версия «жадного» перебора. Но поскольку количество возможных разрезаний с ростом размера квадрата растет экспоненциально быстро (кстати, функция разбиений \(p(N)\) тоже растет экспоненциально быстро: например, \(p(1000)>10^{31}\)), то очень быстро этот алгоритм становится неэффективным. На рис. 6 показаны примеры оптимальных разбиений для \(3\le N\le12\). На сайте wolfram.com есть виджет, позволяющий «поиграться» с разбиениями для разных квадратов.

Рис. 6. Оптимальные (с наименьшим качеством) разбиения для квадратов со стороной от 3 до 12. Рисунок из статьи H. Bassen, Further Insight into the Mondrian Art Problem

Интересен также вопрос и нижних оценок для качества разбиения: можно ли, например, с уверенностью утверждать, что не существует «идеального» квадрата, качество которого равно 0? Пока на этом направлении есть только эмпирические результаты. В упоминавшейся статье Further Insight into the Mondrian Art Problem показано, что для квадратов со стороной \(3\le N\le419\) идеального разбиения не существует.

Интересно, что если разрешить прямоугольникам разбиения иметь нецелые стороны, то идеальное разбиение возможно. Пример показан на рис. 7. Он был предложен в 1971 году Бланш Декарт (Blanche Descartes, 1971. Division of a Square into Rectangles).

Рис. 7. Разбиение квадрата со стороной 210 на неравные прямоугольники одинаковой площади. Площадь каждого из них равна 6300. Рисунок с сайта mathworld.wolfram.com