Задача одной плитки ({g;gcg k;ukw hlnmtn)
Задача одной плитки (англ. einstein problem) — решённая геометрическая проблема поиска одной протоплитки[англ.], которая образует непериодическое множество плиток[англ.], то есть фигуры, копиями которой можно замостить плоскость, но только непериодичным способом.
Предыстория
[править | править код]
Задачу одной плитки можно рассматривать как естественное продолжение второй части восемнадцатой проблемы Гильберта[англ.], в которой был задан вопрос о таком многограннике, копиями которого можно заполнить трёхмерное евклидово пространство, причём никакое заполнение пространства копиями этого многогранника не должно быть изоэдральным[1]. Такие неизоэдральные тела[англ.] были найдены Карлом Райнхардом[англ.] в 1928 году, но эти тела заполняют пространство периодическим образом.
В 1960-е годы логик Ван Хао рассмотрел проблему замощения плоскости квадратами с раскрашенными рёбрами (плитки Вана): имея фиксированный набор таких квадратов (без поворотов и отражений), можно ли замостить ими плоскость так, чтобы квадраты соприкасались рёбрами одинакового цвета? Ван заметил, что если эта проблема алгоритмически неразрешима, то существует апериодический набор плиток Вана.
В 1966 году Роберт Бергер доказал, что проблема Вана алгоритмически неразрешима и нашел апериодический набор плиток Вана, состоящий из 20 426 плиток. В дальнейшем были найдены апериодические наборы из меньшего числа плиток: позже Бергер сократил свой набор до 104; Ганс Лойхли впоследствии нашел апериодический набор, требующий всего 40 плиток Вана; в 1996 году Карел Чулик нашел набор из 13 плиток Вана. Наконец, в 2015 году Э. Жанделем и М. Рао был найден набор из 11 плиток, и было доказано, что для плиток Вана это минимально возможный апериодический набор.
В 1971 году Рафаэль М. Робинсон обнаружил апериодический набор состоящий из шести плиток, отличных от плиток Вана. В 1973 году Роджер Пенроуз открыл плитки Пенроуза, уменьшив минимальное количество плиток, необходимых для непериодического замощения плоскости, до двух. Вопрос о существовании апериодического набора, состоящего только из одной протоплитки, долгое время оставался открытым.
Частичные решения
[править | править код]
В 1988 году Петер Шмитт обнаружил непериодическую протоплитку для трёхмерного евклидова пространства. Хотя никакое заполнение этим телом не допускает параллельный перенос, некоторые заполнения имеют винтовую симметрию[англ.]. Эта операция винтовой симметрии представляет собой композицию параллельного переноса и вращения на угол, несоизмеримый с π, так что никакое число повторений этих операций не приведёт к простому параллельному переносу. Эта конструкция была позднее использована Джоном Конвеем и Людвигом Данцером для построения выпуклой непериодической плитки, плитки Шмитта — Конвея — Данцера. Наличие винтовой симметрии явилось следствием требования непериодичности[2]. Хаим Гудман-Штраусс предложил считать мозаики строго апериодичными, если для них не существует бесконечной циклической группы движений евклидова пространства[англ.], являющихся симметриями мозаики, и называть строго апериодичными только те наборы плиток, которые приводят к строго апериодичным мозаикам, остальные наборы плиток тогда называются слабо апериодичными[3].
В 1996 году Петра Гуммельт построила десятиугольную плитку с рисунком и показала, что при разрешении двух типов перекрытия пар плиток ими можно замостить плоскость, причём только апериодичным образом[4]. Обычно под мозаикой понимается заполнение без перекрытия, так что плитку Гуммельт нельзя считать апериодической протоплиткой.
В начале 2010-х годов Джошуа Соколар и Джоан Тейлор предложили апериодическое множество плиток на евклидовой плоскости, которое состоит только из одной плитки[5]. Конструкция плитки Соколара — Тейлор включает правила соединения, правила, ограничивающие относительную ориентацию двух плиток, и правила соединения рисунков на плитках, и эти правила применяются к парам несмежных плиток. Можно использовать плитки без рисунков и без правил ориентации, но тогда плитки не будут связными. Построение можно распространить на трёхмерное пространство с использованием связных плиток и без правил соединения, но эти плитки могут быть выложены с периодичностью в одном направлении, так что это лишь слабо непериодическая мозаика. Более того, плитки не односвязны.
Полное решение
[править | править код]«Шляпа»
[править | править код]В 2022 году математик-любитель Дэвид Смит обнаружил плитку в форме 13-угольной «шляпы» (англ. hat), состоящую из восьми копий дельтоида с углами 60°–90°–120°–90°, склеенных встык, которые, как казалось, могли непериодически замощать плоскость[6]. Смит обратился за помощью к профессиональным математикам Дж. С. Майерсу, К. С. Каплану и Х. Гудман-Штрауссу, и в 2023 году они совместно опубликовали доказательство, что «шляпа» вместе с её зеркальным отражением образуют набор плиток, который замощает плоскость исключительно непериодически, что является решением задачи одной плитки[7][8]. Более того, они нашли целое семейство протоплиток с таким свойством.
«Привидение»
[править | править код]Найденное решение плиткой «шляпа» (как и всё бесконечное семейство плиток Смита—Майерса—Каплана—Гудман-Штраусса) имело один недостаток: для замощения плоскости некоторые плитки требовали переворота. Если запретить переворот, то в замощении участвовали две разные плитки, являющиеся зеркальным отражением друг друга, что не позволяло назвать решение задачи одной плитки в полной мере окончательным. Однако вскоре Смит с соавторами опубликовали описание ещё одной плитки, устранив этот недостаток. Их новая плитка, названная «привидением» (англ. spectre), допускает только апериодическое замощение плоскости без использования зеркально отражённой плитки, и тем самым окончательно решает задачу одной плитки[9].
Название задачи
[править | править код]Ещё до того, как была найдена фигура, решающая задачу одной плитки, в источниках на английском языке называли такую гипотетическую фигуру «einstein» — это игра слов: нем. ein stein означает «один камень»[10], и так же записывается фамилия Альберта Эйнштейна.
Примечания
[править | править код]- ↑ Senechal, 1996, pp. 22–24.
- ↑ Radin, 1995, pp. 3543–3548.
- ↑ Goodman-Strauss, 2000.
- ↑ Gummelt, 1996, pp. 1–17.
- ↑ Socolar, Taylor, 2011, pp. 2207–2231.
- ↑ Hobbyist Finds Math’s Elusive ‘Einstein’ Tile Архивная копия от 6 апреля 2023 на Wayback Machine // Quanta Magazine
- ↑ David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss. An aperiodic monotile (2023). Дата обращения: 21 марта 2023. Архивировано 21 марта 2023 года.
- ↑ David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss. An aperiodic monotile // Combinatorial Theory. — 2024. — Vol. 4. — P. #6. — doi:10.5070/C64163843.
- ↑ David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss. A chiral aperiodic monotile (2023). Дата обращения: 30 мая 2023. Архивировано 30 мая 2023 года.
- ↑ Newly discovered 'einstein' tile is a 13-sided shape that solves a decades-old math problem | Live Science. Дата обращения: 1 апреля 2023. Архивировано 1 апреля 2023 года.
Литература
[править | править код]- Petra Gummelt. Penrose Tilings as Coverings of Congruent Decagons // Geometriae Dedicata. — 1996. — Vol. 62. — Вып. 1. — doi:10.1007/BF00239998.
- Marjorie Senechal. Quasicrystals and Geometry. — corrected paperback. — Cambridge University Press, 1996. — ISBN 0-521-57541-9.
- Charles Radin. Aperiodic tilings in higher dimensions // Proceedings of the American Mathematical Society. — American Mathematical Society, 1995. — Vol. 123. — Вып. 11. — doi:10.2307/2161105. — .
- Chaim Goodman-Strauss. Open Questions in Tiling. — 2000. Архивировано 18 апреля 2007 года. Архив:
- Joshua E. S. Socolar, Joan M. Taylor. An Aperiodic Hexagonal Tile // Journal of Combinatorial Theory, Series A. — 2011. — Vol. 118. — doi:10.1016/j.jcta.2011.05.001. — arXiv:1003.4279.
