Нонамино

Нонамино (или 9-мино) — девятиклеточные полимино, или многоугольники, составленные из 9 равных квадратов, соединённых сторонами[1][2].

Вариант судоку с регионами в форме нонамино

Если не различать фигуры, получаемые друг из друга поворотами и отражениями, то существует 1285 нонамино[1][2][3]. Если условиться различать зеркальные отражения, число нонамино возрастает до 2500[4], а если различать и вращения — то до 9910[5][6][7].

Подмножества

37 из 1285 нонамино содержат в себе отверстия[7][8]. Одно из нонамино содержит отверстие в форме домино; в полимино меньших размеров встречаются лишь одиночные отверстия.

Только одно нонамино является многоугольником, длины всех сторон которого равны единице (до нонамино этим свойством обладают мономино, X-пентамино и одно из 369 октамино)[9][10].

Симметрии

1285 двусторонних нонамино можно разбить на несколько подмножеств по их группам симметрии[6]:

  • 1196 нонамино асимметричны — их группа симметрии тривиальна[11];
  • 38 нонамино имеют одну ось симметрии, параллельную рёбрам квадратного паркета, и их группа симметрии состоит из двух элементов — тождественного преобразования и отражения[12];

  • 26 нонамино имеют одну диагональную ось симметрии, и их группа симметрии также состоит из двух элементов[13];

  • 19 нонамино имеют центральную симметрию второго порядка, и их группа симметрии состоит из двух элементов — тождественного преобразования и поворота на 180°[14];

  • 4 нонамино имеют две взаимно перпендикулярные оси симметрии, параллельные сторонам полимино; их группа симметрий состоит из четырёх элементов — тождественного преобразования, двух отражений и поворота на 180°[15];

  • 2 нонамино имеют четыре оси симметрии (две параллельные сторонам полимино и две диагональные) и центральную симметрию четвёртого порядка. Их группа симметрий состоит из 8 элементов[16].

В отличие от октамино, среди нонамино нет фигур с центральной симметрией порядка 4 или фигур с двумя диагональными осями симметрии.

Число двусторонних или свободных нонамино (фигур, которые можно поворачивать и переворачивать), таким образом, равно

число односторонних нонамино (фигур, которые можно поворачивать, но нельзя переворачивать) можно найти по формуле

а число фиксированных нонамино (фигур, которые нельзя ни поворачивать, ни переворачивать) — по формуле

Замощение плоскости

1050 двусторонних нонамино (все, кроме 235, в число которых входят и 37 «дырявых» нонамино) покрывают плоскость[17][18][19]; 1048 из этих 1050 нонамино либо удовлетворяют критерию Конвея самостоятельно, либо способны сформировать «заплатку» из двух копий нонамино, удовлетворяющую критерию Конвея. Два исключительных нонамино, которые покрывают плоскость, несмотря на отрицательный результат проверки по критерию Конвея, показаны на рисунке справа; 9 — наименьшее число, для которого существуют подобные исключения[20].

Составление конфигураций из нонамино

37 нонамино содержат «отверстия», поэтому из всех 1285 нонамино нельзя сложить ни одного прямоугольника[1]. Тем не менее, в 1972-1973 гг. Д. Бёрд (David Bird) построил несколько симметричных конфигураций с помощью всех 1285 нонамино; два построения умещались в квадрате 109 × 109[2][21]. В 2005 году Peter Esser построил из всех 1285 нонамино пять конгруэнтных прямоугольников 17 × 137, каждый из которых содержал 12 симметрично расположенных отверстий общей площадью в 16 клеток[22]; он же построил из 1248 односвязных нонамино 16 прямоугольников 18 × 39[22]. Patrick Hamlyn построил из 1248 односвязных нонамино 48 прямоугольников 18 × 13; не исключена возможность построения 96 одинаковых прямоугольников[22].

Псевдононамино

Псевдополимино — обобщение полимино, набор полей бесконечной шахматной доски, которые может обойти король[1]. Существует 118 133 двусторонних псевдононамино[23], 235 456 односторонних псевдононамино[24] и 940 982 фиксированных псевдононамино[25].

Примечания
  1. Голомб, 1975.
  2. Golomb, 1994.
  3. Последовательность A000105 в OEIS
  4. Последовательность A000988 в OEIS
  5. Последовательность A001168 в OEIS
  6. Redelmeier, 1981.
  7. Weisstein, Eric W. Polyomino (англ.) на сайте Wolfram MathWorld.
  8. Последовательность A001419 в OEIS
  9. Col. George Sicherman. Catalogue of Unitary Polyominoes (29 июля 2014).
  10. Последовательность A245620 в OEIS
  11. Последовательность A006749 в OEIS
  12. Последовательность A006746 в OEIS
  13. Последовательность A006748 в OEIS
  14. Последовательность A006747 в OEIS
  15. Последовательность A056877 в OEIS
  16. Последовательность A142886 в OEIS
  17. Rawsthorne, 1988.
  18. Joseph Myers. Polyomino, polyhex and polyiamond tiling.
  19. Последовательности A054359, A054360, A054361 в OEIS
  20. Rhoads, 2005.
  21. David Bird's Polyomino Constructions. The Poly Pages.
  22. Polyominoes. The Poly Pages.
  23. Последовательность A030222 в OEIS
  24. Последовательность A030233 в OEIS
  25. Последовательность A006770 в OEIS

Литература
  • Голомб С.В.. Полимино = Polyominoes / Пер. с англ. В. Фирсова. Предисл. и ред. И. Яглома. — М.: Мир, 1975. — 207 с.
  • Solomon W. Golomb. Polyominoes. — 2nd ed. — Princeton, New Jersey: Princeton University Press, 1994. — ISBN 0-691-02444-8.
  • D. Hugh Redelmeier. Counting polyominoes: yet another attack // Discrete Mathematics : журнал. — 1981. — Vol. 36. — P. 191–203. — doi:10.1016/0012-365X(81)90237-5.
  • Daniel A. Rawsthorne. Tiling complexity of small n-ominoes (n<10) // Discrete Mathematics : журнал. — 1988. — Vol. 70. — P. 71–75. — doi:10.1016/0012-365X(88)90081-7.
  • Glenn C. Rhoads. Planar tilings by polyominoes, polyhexes, and polyiamonds // Journal of Computational and Applied Mathematics : журнал. — 2005. — Vol. 174. — P. 329–353. — doi:10.1016/j.cam.2004.05.002.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.