Возведение квадрата в квадрат

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

Идеальные квадраты

«Идеальный» квадрат — это квадрат, в котором каждый из меньших квадратов имеет разный размер.

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

Первый опубликованный идеальный квадрат, составной квадрат со стороной 4205 и порядком 55, был найден Роландом Спрэгом в 1939 году. ^[1]

Мартин Гарднер опубликовал обширную статью У.Т. Тутте о ранней истории возведения в квадрат квадрата в своей «Математические игры» колонке в ноябре 1958 года. ^[2]

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

«Простой» квадрат — это квадрат, в котором ни одно подмножество более чем одного квадрата не образует прямоугольник или квадрат. Когда у квадратного квадрата есть квадратное или прямоугольное подмножество, он является «составным».

В 1978 году А. Д. Дуйвестейн [ де ] с помощью компьютерного поиска обнаружил простой идеальный квадрат со стороной 112 с наименьшим количеством квадратов. Его мозаика использует 21 квадрат и оказалась минимальной. ^[3] Этот квадратный квадрат образует логотип Тринити-математического общества . Он также появляется на обложке журнала комбинаторной теории .

Дуйвестейн также нашел два простых идеальных квадрата со сторонами 110, но каждый из которых состоит из 22 квадратов. Теофил Хардинг Уиллкокс, математик-любитель и сказочный шахматный композитор, нашел еще одну. В 1999 году И. Гамбини доказал, что эти три являются наименьшими по длине стороны правильными квадратами. ^[4]

Идеальный составной квадрат с наименьшим количеством квадратов был обнаружен Т.Х. Уиллкоксом в 1946 году и состоит из 24 квадратов; однако только в 1982 году Дуйвестейн, Паскуале Джозеф Федерико и П. Леу математически доказали, что это пример низшего порядка. ^[5]

Одеяло миссис Перкинс

Когда ограничение, заключающееся в том, что все квадраты имеют разные размеры, ослаблено, квадрат, в котором длины сторон меньших квадратов не имеют общего делителя больше 1, называется «одеялом миссис Перкинс». Другими словами, наибольший общий делитель всех меньших сторон должен быть равен 1. Задача о лоскутном одеяле миссис Перкинс требует найти лоскутное одеяло миссис Перкинс с наименьшим количеством частей для данного $n\times n$ квадрат. Необходимое количество штук не менее $\log _{2}n$ , ^[6] и самое большее $6\log _{2}n$ . ^[7] Компьютерный поиск позволил найти точные решения для малых значений $n$ (достаточно маленький, потребуется до 18 штук). ^[8] Для $n=1,2,3,\dots$ необходимое количество штук:

1, 4, 6, 7, 8, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, ... (последовательность A005670 в OEIS )

Не более двух разных размеров.

Квадрат, разрезанный на 10 частей (таблица HTML)

Для любого целого числа $n$ кроме 2, 3 и 5, можно разрезать квадрат на $n$ квадраты одного или двух разных размеров. ^[9]

Квадратизация плоскости

В 1975 году Соломон Голомб поднял вопрос, можно ли разбить всю плоскость квадратами, по одному на каждую целую длину ребра, который он назвал гипотезой гетерогенного замощения . Эта проблема позже была освещена Мартином Гарднером в его колонке в Scientific American и появилась в нескольких книгах, но она не могла быть решена более 30 лет.

В книге «Tilings and Patterns» , опубликованной в 1987 году, Бранко Грюнбаум и Г.К. Шепард заявили, что во всех известных на тот момент совершенных целочисленных мозаиках плоскости размеры квадратов росли экспоненциально . Например, плоскость можно замостить разными целыми квадратами, но не для каждого целого числа, рекурсивно беря любой идеальный квадрат и увеличивая его так, чтобы ранее наименьшая плитка теперь имела размер исходного квадрата, а затем заменяя эту плитку на копия оригинального квадрата.

В 2008 году Джеймс Хенле и Фредерик Хенле доказали, что это действительно возможно. Их доказательство является конструктивным и основано на «раздувании» L-образной области, образованной двумя расположенными рядом и горизонтально расположенными квадратами разных размеров, до идеального замощения большей прямоугольной области, а затем присоединения к квадрату наименьшего размера, не но использовался для получения другой, более крупной L-образной области. Квадраты, добавленные в процессе раздувания, имеют размеры, которые еще не фигурировали в построении, и процедура настроена так, что полученные прямоугольные области расширяются во всех четырех направлениях, что приводит к замощению всей плоскости. ^[10]

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

Возведение куба в трех измерениях является аналогом возведения в квадрат квадрата: то есть для куба C возникает проблема его разделения на конечное число меньших кубов, причем не существует двух конгруэнтных.

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

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

Теперь предположим, что существует идеальное рассечение прямоугольного кубоида на кубы. Сделайте грань C ее горизонтальным основанием. Основание разделено на правильный прямоугольный прямоугольник R лежащими на нем кубиками. Наименьший квадрат s ₁ в R окружен кубиками большего размера и, следовательно, более высокого размера . Следовательно, верхняя грань куба на s ₁ разделена на полный квадрат лежащими на ней кубиками. Пусть s ₂ — наименьший квадрат в этом разрезе. Согласно приведенному выше утверждению, он со всех четырех сторон окружен квадратами, которые больше s ₂ и, следовательно, выше.

Последовательность квадратов s ₁ , s ₂ , ... бесконечна, а количество соответствующих кубиков бесконечно. Это противоречит нашему первоначальному предположению. ^[11]

Если бы 4-мерный гиперкуб мог быть идеально гиперкубирован, то его «грани» были бы идеальными кубами; это невозможно. Точно так же не существует решения для всех кубов более высоких измерений.

См. также

Ссылки

^ Перейти обратно: ^а ^б Спраг, Р. (1939). «Пример разложения квадрата на разные квадраты». Математический журнал . 45 :607-608. дои : 10.1007/BF01580305 . МР 0000470 . Английский перевод Дэвида Мьюза « Пример разрезания квадрата на попарно неравные квадраты ».
^ Гарднер, Мартин (ноябрь 1958 г.). «Как прямоугольники, в том числе и квадраты, можно разделить на квадраты неравной величины». Математические игры. Научный американец . 199 (5): 136–144. JSTOR 24944827 . У.Т.Татте не указан как автор колонки, но она почти полностью состоит из длинной цитаты из нескольких абзацев, авторство которой принадлежит Тутте.
^ Дуйвестейн, AJW (1978). «Простой правильный квадрат низшего порядка» . Журнал комбинаторной теории, серия B. 25 (2): 240–243. дои : 10.1016/0095-8956(78)90041-2 . МР 0511994 .
^ Гамбини, Ян (1999). «Метод разрезания квадратов на отдельные квадраты» . Дискретная прикладная математика . 98 (1–2): 65–80. дои : 10.1016/S0166-218X(99)00158-4 . МР 1723687 .
^ Дуйвестейн, AJW; Федерико, Пи Джей ; Леу, П. (1982). «Составные совершенные квадраты». Американский математический ежемесячник . 89 (1): 15–32. дои : 10.1080/00029890.1982.11995375 . JSTOR 2320990 . МР 0639770 .
^ Конвей, Дж. Х. (1964). «Одеяло миссис Перкинс». Труды Кембриджского философского общества . 60 : 363–368. дои : 10.1017/S0305004100037877 . МР 0167425 .
^ Траструм, Великобритания (1965). «Одеяло миссис Перкинс». Труды Кембриджского философского общества . 61 : 7–11. дои : 10.1017/s0305004100038573 . МР 0170831 .
^ Винн, Эд (2014). «Исчерпывающее создание квадратных разрезов« лоскутного одеяла миссис Перкинс »для низких заказов». Дискретная математика . 334 : 38–47. arXiv : 1308.5420 . дои : 10.1016/j.disc.2014.06.022 . МР 3240464 .
^ Генри, Дж. Б.; Тейлор, Пи Джей (2009). Испытание! 1999-2006 Книга 2 . Австралийский математический фонд. п. 84. ИСБН 978-1-876420-23-9 .
^ Хенле, Фредерик В.; Хенле, Джеймс М. (2008). «Квадрат плоскости» (PDF) . Американский математический ежемесячник . 115 (1): 3–12. дои : 10.1080/00029890.2008.11920491 . JSTOR 27642387 . S2CID 26663945 .
^ Брукс, РЛ ; Смит, Калифорния ; Стоун, Ага ; Тутте, WT (1940). «Разрезание прямоугольников на квадраты» . Математический журнал Дьюка . 7 : 312–340. дои : 10.1215/S0012-7094-40-00718-9 . МР 0003040 .

Внешние ссылки

Идеальные квадраты:
- Букамп, CJ; Дуйвестейн, AJW (декабрь 1994 г.). «Альбом простых совершенных квадратов порядка 26» (PDF) . Отчет EUT 94-WSK-02. , Технологический университет Эйндховена, факультет математики и информатики
- http://www.squaring.net/
- http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html
- http://www.math.uwaterloo.ca/navigation/ideas/articles/honsberger2/index.shtml
- https://web.archive.org/web/20030419012114/http://www.math.niu.edu/~rusin/known-math/98/square_dissect
Нигде не аккуратные квадраты:
- http://karlscherer.com/
Одеяло миссис Перкинс:
- Одеяло миссис Перкинс на MathWorld

[sprague-1] Перейти обратно: ^а ^б Спраг, Р. (1939). «Пример разложения квадрата на разные квадраты». Математический журнал . 45 :607-608. дои : 10.1007/BF01580305 . МР 0000470 . Английский перевод Дэвида Мьюза « Пример разрезания квадрата на попарно неравные квадраты ».

[gardner-tutte-2] Гарднер, Мартин (ноябрь 1958 г.). «Как прямоугольники, в том числе и квадраты, можно разделить на квадраты неравной величины». Математические игры. Научный американец . 199 (5): 136–144. JSTOR 24944827 . У.Т.Татте не указан как автор колонки, но она почти полностью состоит из длинной цитаты из нескольких абзацев, авторство которой принадлежит Тутте.

[duijvestijn-3] Дуйвестейн, AJW (1978). «Простой правильный квадрат низшего порядка» . Журнал комбинаторной теории, серия B. 25 (2): 240–243. дои : 10.1016/0095-8956(78)90041-2 . МР 0511994 .

[gambini-4] Гамбини, Ян (1999). «Метод разрезания квадратов на отдельные квадраты» . Дискретная прикладная математика . 98 (1–2): 65–80. дои : 10.1016/S0166-218X(99)00158-4 . МР 1723687 .

[dfl-5] Дуйвестейн, AJW; Федерико, Пи Джей ; Леу, П. (1982). «Составные совершенные квадраты». Американский математический ежемесячник . 89 (1): 15–32. дои : 10.1080/00029890.1982.11995375 . JSTOR 2320990 . МР 0639770 .

[conway-6] Конвей, Дж. Х. (1964). «Одеяло миссис Перкинс». Труды Кембриджского философского общества . 60 : 363–368. дои : 10.1017/S0305004100037877 . МР 0167425 .

[trustrum-7] Траструм, Великобритания (1965). «Одеяло миссис Перкинс». Труды Кембриджского философского общества . 61 : 7–11. дои : 10.1017/s0305004100038573 . МР 0170831 .

[wynn-8] Винн, Эд (2014). «Исчерпывающее создание квадратных разрезов« лоскутного одеяла миссис Перкинс »для низких заказов». Дискретная математика . 334 : 38–47. arXiv : 1308.5420 . дои : 10.1016/j.disc.2014.06.022 . МР 3240464 .

[henry-taylor-9] Генри, Дж. Б.; Тейлор, Пи Джей (2009). Испытание! 1999-2006 Книга 2 . Австралийский математический фонд. п. 84. ИСБН 978-1-876420-23-9 .

[henle-10] Хенле, Фредерик В.; Хенле, Джеймс М. (2008). «Квадрат плоскости» (PDF) . Американский математический ежемесячник . 115 (1): 3–12. дои : 10.1080/00029890.2008.11920491 . JSTOR 27642387 . S2CID 26663945 .

[bsst-11] Брукс, РЛ ; Смит, Калифорния ; Стоун, Ага ; Тутте, WT (1940). «Разрезание прямоугольников на квадраты» . Математический журнал Дьюка . 7 : 312–340. дои : 10.1215/S0012-7094-40-00718-9 . МР 0003040 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]