Нонамино

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Вариант судоку с регионами в форме нонамино

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

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

Подмножества[править | править код]

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

The 37 Nonominoes with Holes.svg

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

Симметрии[править | править код]

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

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

Reflection-symmetric-nonominoes-90-deg.svg

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

Reflection-symmetric nonominoes 45-deg.svg

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

C2-Rotation-symmetric nonominoes.svg

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

D2 Rotation and Reflection Symmetric Nonominoes.svg

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

D4 Rotation and Reflection Symmetric Nonominoes.svg

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

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

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

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

Замощение плоскости[править | править код]

Conway criterion false negative nonominoes.svg

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. 1 2 3 4 Голомб, 1975.
  2. 1 2 3 Golomb, 1994.
  3. Последовательность A000105 в OEIS
  4. Последовательность A000988 в OEIS
  5. Последовательность A001168 в OEIS
  6. 1 2 Redelmeier, 1981.
  7. 1 2 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. 1 2 3 Polyominoes. The Poly Pages.
  23. Последовательность A030222 в OEIS
  24. Последовательность A030233 в OEIS
  25. Последовательность A006770 в OEIS

Литература[править | править код]