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

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

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

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

Впервые зафиксировано, что его изучали Р.Л. Брукс , К.Э.Б. Смит , А.Х. Стоун и У.Т. Тутт (писавшие под коллективным псевдонимом « Бланш Декарт ») в Кембриджском университете между 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 ]