Введение

Математическая задача

Разбиение квадрата на квадраты — это задача покрытия целочисленного квадрата другими целочисленными квадратами. (Целочисленный квадрат — это квадрат, стороны которого имеют целую длину.) Название было придумано по аналогии с квадратурой круга, в шутливой форме. Разбиение квадрата на квадраты — простая задача, если не накладываются дополнительные условия. Наиболее изученным ограничением является требование совершенства разбиения, то есть все меньшие квадраты должны быть разного размера. Связанной задачей является разбиение плоскости на квадраты, которое возможно даже при условии, что каждое натуральное число встречается ровно один раз в качестве размера квадрата в покрытии. Порядок разбиения квадрата на квадраты — это количество составляющих его квадратов.

Прекрасное квадраты квадраты

"Идеальный" квадратный квадрат – это квадрат, в котором каждый из меньших квадратов имеет свой собственный размер. Впервые его изучение зафиксировано у Р. Л. Брукса, К. А. Б. Смита, А. Х. Стоуна и В. Т. Тютте (публиковавшихся под коллективным псевдонимом "Бланш Декарт") в Кембриджском университете в период с 1936 по 1938 год. Они преобразовали мозаику из квадратов в эквивалентную электрическую схему, которую назвали "диаграммой Смита", рассматривая квадраты как резисторы, соединенные со своими соседями по верхним и нижним сторонам, а затем применили законы Кирхгофа и методы разложения электрических цепей к этой схеме. Первые найденные ими идеальные квадратные квадраты были порядка 69. Первый опубликованный идеальный квадратный квадрат, составной, со стороной 4205 и порядком 55, был найден Роландом Спрагом в 1939 году. Мартин Гарднер опубликовал подробную статью, написанную В. Т. Тютте об истории задачи разбиения квадрата на квадраты, в своей колонке "Математические игры" в ноябре 1958 года.

Простые квадраты квадратов

"Простой" квадратный квадрат – это такой, где никакое подмножество, состоящее более чем из одного квадрата, не образует прямоугольник или квадрат, в противном случае он считается "сложным". В 1978 году де обнаружил простой совершенный квадратный квадрат со стороной 112, содержащий наименьшее количество квадратов, используя компьютерный поиск. Его разбиение состоит из 21 квадрата, и было доказано, что оно минимально. Этот квадратный квадрат является логотипом Тринити Математического Общества. Он также был изображен на обложке журнала Journal of Combinatorial Theory. Дюйстейн также обнаружил два простых совершенных квадратных квадрата со сторонами 110, каждый из которых состоит из 22 квадратов. Теофилус Хардинг Уиллкокс, математик-любитель и композитор шахматных задач, обнаружил еще один. В 1999 году И. Гамбини доказал, что эти три являются наименьшими совершенными квадратными квадратами по длине стороны. Совершенный сложный квадратный квадрат с наименьшим количеством квадратов был открыт Т. Х. Уиллкоксом в 1946 году и содержит 24 квадрата; однако математически доказательство того, что это пример наименьшего порядка, было получено только в 1982 году Дюйстейном, Паскуале Джозефом Федерико и П. Лиувом.

Покрывало миссис Перкинс

Когда снимается ограничение на то, что все квадраты должны быть разных размеров, квадрат, составленный из квадратов, у которых длины сторон меньших квадратов не имеют общего делителя, большего 1, называется "квилт миссис Перкинс". Иными словами, наибольший общий делитель всех длин сторон меньших квадратов должен быть равен 1. Задача о квилте миссис Перкинс заключается в нахождении квилта миссис Перкинс с минимальным количеством частей для заданного квадрата. Количество необходимых частей не может быть меньше , и не превышает . Компьютерный поиск обнаружил точные решения для небольших значений (достаточно малых, чтобы требовалось до 18 частей). Для количество необходимых частей равно:

Квадрат самолета

В 1975 году Соломон Голомб задался вопросом, можно ли полностью покрыть плоскость квадратами, используя по одному квадрату каждого целого размера стороны, что он назвал гипотезой неоднородной мощения. Эта проблема позднее была популяризирована Мартином Гарднером в его колонке в журнале Scientific American и появилась в нескольких книгах, но более 30 лет оставалась нерешенной. В книге «Мощения и узоры», опубликованной в 1987 году, Бранко Грюнбаум и Г. С. Шепард отметили, что во всех известных на тот момент совершенных целочисленных мощениях плоскости размеры квадратов росли экспоненциально. Например, плоскость можно покрыть квадратами различных целочисленных размеров, но не для каждого целого числа, рекурсивно беря любой идеальный квадрат и увеличивая его так, чтобы ранее наименьший квадрат теперь имел размер исходного квадрата, а затем заменяя этот квадрат копией исходного квадрата. В 2008 году Джеймс Хенле и Фредерик Хенле доказали, что это действительно возможно. Их доказательство конструктивно и основано на «раздувании» L-образной области, образованной двумя расположенными рядом и горизонтально выровненными квадратами разных размеров, до совершенного мощения большей прямоугольной области, а затем присоединении квадрата наименьшего еще не использованного размера для получения другой, большей L-образной области. Квадраты, добавляемые в процессе раздувания, имеют размеры, которые еще не встречались в построении, и процедура устроена таким образом, чтобы полученные прямоугольные области расширялись во всех четырех направлениях, что приводит к мощению всей плоскости.

Кубирование кубика

Кубирование куба является трехмерным аналогом квадратизации квадрата: то есть, для заданного куба C, задача заключается в его разделении на конечное число меньших кубов, причем никакие два из них не должны быть конгруэнтными. В отличие от квадратизации квадрата, сложной, но разрешимой задачи, не существует идеального кубирования куба и, в более общем смысле, не существует разбиения прямоугольного параллелепипеда C на конечное число неравных кубов. Для доказательства этого начнем со следующего утверждения: для любого совершенного разбиения прямоугольника на квадраты, наименьший квадрат в этом разбиении не лежит на стороне прямоугольника. Действительно, каждый угловой квадрат имеет прилегающий к нему меньший квадрат, а наименьший квадрат на стороне прилегает к меньшим квадратам, не находящимся на стороне. Теперь предположим, что существует совершенное разбиение прямоугольного параллелепипеда на кубы. Сделаем одну из граней C его горизонтальным основанием. Основание разделено на прямоугольник R, составленный из квадратов, посредством кубов, лежащих на нем. Наименьший квадрат s1 в R окружен большими, и, следовательно, более высокими кубами. Следовательно, верхняя грань куба, на котором лежит s1, разделена на прямоугольник, составленный из квадратов, посредством кубов, лежащих на нем. Пусть s2 будет наименьшим квадратом в этом разбиении. Согласно вышеуказанному утверждению, он окружен со всех 4 сторон квадратами, которые больше, чем s2 и, следовательно, выше. Последовательность квадратов s1, s2, … бесконечна, а соответствующих кубов бесконечно много. Это противоречит нашему исходному предположению. Если бы 4-мерный гиперкуб мог быть идеально гиперкубирован, то его "грани" были бы идеальными кубированными кубами; это невозможно. Аналогично, не существует решения для кубов более высоких размерностей.