Пентамино

12 пентамино могут образовывать 18 различных фигур, причем 6 из них (хиральные пентамино) зеркально отражены.

происходящее от греческого слова « 5 » и « домино », Пентамино (или 5-омино ), представляет собой полимино 5-го порядка; то есть многоугольник на плоскости, одинакового размера состоящий из 5 квадратов , соединенных ребром к краю. Если вращения и отражения не считаются отдельными формами, существует 12 различных свободных пентамино. Когда отражения считаются отдельными, получается 18 односторонних пентамино. Если вращения также считаются отдельными, существует 63 фиксированных пентамино.

пентамино Головоломки и игры с мозаикой популярны в развлекательной математике . Обычно видеоигры , такие как имитации Тетриса и Rampart, считают зеркальные отражения отдельными и поэтому используют полный набор из 18 односторонних пентамино. (В самом тетрисе используются фигуры из 4 квадратов.)

Каждое из двенадцати пентамино удовлетворяет критерию Конвея ; следовательно, каждое пентамино способно замостить плоскость . Каждое киральное пентамино может замостить плоскость, не отражаясь.

История

Сравнение схем маркировки 12 возможных форм пентамино. Первое соглашение об именах используется в этой статье. Второй метод — метод Конвея.

Самая ранняя головоломка, содержащая полный набор пентамино, появилась в Генри Дюдени книге «Кентерберийские головоломки », опубликованной в 1907 году. Самые ранние мозаики прямоугольников с полным набором пентамино появились в приложении «Problemist Fairy Chess Supplement» в 1935 году, а дальнейшие проблемы с мозаикой были исследованы в PFCS и ее преемнике, Fairy Chess Review .

Пентомино были формально определены американским профессором Соломоном В. Голомбом, начиная с 1953 года, а затем в его книге 1965 года «Полимино: головоломки, закономерности, проблемы и упаковки» . Они были представлены широкой публике Мартином Гарднером в его колонке «Математические игры» в журнале Scientific American в октябре 1965 года . Голомб придумал термин «пентамино» от древнегреческого πέντε / pénte , «пять», и -omino от домино , причудливо интерпретируя букву «d-» в слове «домино», как если бы это была форма греческого префикса «ди- " (два). Голомб назвал 12 свободных пентамино в честь букв латинского алфавита , на которые они похожи, используя мнемонику FILiPiNo вместе с концом алфавита (TUVWXYZ).

Джон Хортон Конвей предложил альтернативную схему обозначения пентамино, используя O вместо I, Q вместо L, R вместо F и S вместо N. Сходство с буквами более натянутое, особенно для пентамино O, но это Преимущество схемы состоит в использовании 12 последовательных букв алфавита. Он традиционно используется при обсуждении «Игры жизни» Конвея , где, например, говорится о R-пентамино вместо F-пентамино.

Симметрия

• F, L, N, P и Y можно ориентировать 8 способами: 4 путем вращения и еще 4 для зеркального отображения. Их группа симметрии состоит только из тождественного отображения .
• T и U можно ориентировать четырьмя способами путем вращения. У них есть ось отражения, совмещенная с линиями сетки. Их группа симметрии состоит из двух элементов: единицы и отражения в линии, параллельной сторонам квадратов.
• V и W также можно ориентировать четырьмя способами путем вращения. Они имеют ось симметрии отражения под углом 45° к линиям сетки. Их группа симметрии состоит из двух элементов: единицы и диагонального отражения.
• Z можно ориентировать 4 способами: 2 путем вращения и еще 2 для зеркального отображения. Он обладает точечной симметрией, также известной как вращательная симметрия второго порядка. Его группа симметрии состоит из двух элементов: единицы и поворота на 180°.
• Я могу ориентироваться двумя способами путем вращения. Он имеет две оси симметрии отражения, обе выровнены по линиям сетки. Его группа симметрии состоит из четырех элементов: идентичности, двух отражений и поворота на 180°. Это группа диэдра второго порядка, также известная как четырехгруппа Клейна .
• X может быть ориентирован только одним способом. Он имеет четыре оси отражательной симметрии, выровненные по линиям сетки и диагоналям, а также вращательную симметрию четвертого порядка. Его группа симметрии, группа диэдра четвертого порядка, состоит из восьми элементов.

Пентамино F, L, N, P, Y и Z являются хиральными ; сложение их отражений (F', J, N', Q, Y', S) доводит количество односторонних пентамино до 18. Если считать также различными вращения, то пентамино из первой категории считаются восьмикратными, из следующие три категории (T, U, V, W, Z) учитываются вчетверо, I учитывается дважды, а X учитывается только один раз. В результате получается 5×8 + 5×4 + 2 + 1 = 63 фиксированных пентамино.

Проиллюстрированы восемь возможных ориентаций пентамино F, L, N, P и Y, а также четыре возможных ориентации пентамино T, U, V, W и Z:

• Восемь возможных ориентаций
• 
  F-пентамино
• 
  L-пентамино
• 
  N-пентамино
• 
  П-пентамино
• 
  Y-пентамино

• Четыре возможных направления
• 
  Т-пентамино
• 
  U-пентамино
• 
  V-pentomino
• 
  W-пентамино
• 
  Z-пентамино

Для 2D-фигур вообще есть еще две категории:

• Ориентируется двумя способами путем поворота на 90°, с двумя осями симметрии отражения, обе совмещены с диагоналями. Для этого типа симметрии требуется как минимум гептамино .
• Ориентироваться двумя способами, которые являются зеркальными отражениями друг друга, например свастика . Для этого типа симметрии требуется как минимум октамино .

Игры

Пазл с плиткой (2D)

Пример мозаики

Стандартная головоломка пентамино заключается в том, чтобы замостить прямоугольную коробку пентамино, то есть покрыть ее без перекрытия и без пробелов. Площадь каждого из 12 пентамино равна 5 квадратам, поэтому площадь коробки должна составлять 60 единиц. Возможные размеры: 6×10, 5×12, 4×15 и 3×20.

Случай 6×10 был впервые решен в 1960 году Колином Брайаном Хазелгроувом и Дженифер Хазелгроув . Существует ровно 2339 решений, исключая тривиальные варианты, полученные вращением и отражением всего прямоугольника, но включая вращение и отражение подмножества пентамино (что иногда дает простое дополнительное решение). В ящике 5×12 содержится 1010 решений, в ящике 4×15 — 368 решений, а в ящике 3×20 — всего 2 решения (одно показано на рисунке, а другое можно получить из решения, показанного вращением). в целом блок, состоящий из пентамино L, N, F, T, W, Y и Z).

Несколько более простая (более симметричная) головоломка — прямоугольник 8х8 с отверстием 2х2 в центре — была решена Даной Скотт еще в 1958 году. Имеется 65 решений. Алгоритм Скотта был одним из первых применений компьютерной программы поиска с возвратом . Вариации этой головоломки позволяют разместить четыре отверстия в любом положении. Одна из внешних ссылок использует это правило.

Эффективные алгоритмы для решения таких проблем были описаны, например, Дональдом Кнутом . Эти головоломки пентамино, работающие на современном оборудовании , теперь можно решить за считанные секунды.

Неразрешимые закономерности

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

Набор пентамино — единственный свободный набор полимино, который можно упаковать в прямоугольник, за исключением тривиальных наборов мономино и домино , каждый из которых состоит только из одного прямоугольника.

Пазл о заполнении коробок (3D)

Примеры решения головоломок с пятикубами указанных размеров, нарисованных по одному слою.

Пентакуб – это многокуб из пяти кубов. Из 29 пентакубов ровно двенадцать пентакубов являются плоскими (1-слойными) и соответствуют двенадцати пентамино, выдавленным на глубину одного квадрата.

Головоломка с пентакубами или 3D- головоломка с пентамино представляет собой заполнение трехмерной коробки 12 плоскими пентакубами, т.е. покрытие ее без перекрытия и без пробелов. Поскольку каждый пентакуб имеет объем 5 единичных кубов, объем коробки должен составлять 60 единиц. Возможные размеры: 2×3×10 (12 решений), 2×5×6 (264 решения) и 3×4×5 (3940 решений).

В качестве альтернативы можно также рассмотреть комбинации из пяти кубов, которые сами по себе являются трехмерными, то есть те, которые включают в себя больше, чем просто 12 «плоских» однослойных толстых комбинаций кубов. Однако в дополнение к 12 «плоским» пентакубам, образованным путем выдавливания пентамино, существует 6 наборов хиральных пар и 5 дополнительных частей, образующих в общей сложности 29 потенциальных частей пентакуба, что в общей сложности дает 145 кубов (= 29 × 5). ; поскольку 145 можно упаковать только в коробку размером 29×5×1, его нельзя сформировать путем включения неплоских пентамино.

Коммерческие настольные игры

Существуют настольные игры на ловкость, полностью основанные на пентамино. Такие игры часто называют просто «Пентомино».

Одна из игр проводится на сетке 8х8 двумя или тремя игроками. Игроки по очереди размещают пентамино на доске так, чтобы они не перекрывались с существующими плитками и чтобы ни одна плитка не использовалась более одного раза. Цель — стать последним игроком, положившим плитку на доску. Эта версия пентамино называется «Игра Голомба».

Версия для двух игроков была слабо решена в 1996 году Хилари Орман. Исследование около 22 миллиардов позиций на доске доказало, что это победа первого игрока.

Пентамино и подобные формы также являются основой ряда других игр, узоров и головоломок. Например, во французской настольной игре «Блокус» используются 4 цветных набора полимино , каждый из которых состоит из пентамино (12), тетромино (5), триомино (2), домино (1) и мономино (1). Как и в игре «Пентомино» , цель состоит в том, чтобы использовать все ваши плитки, и бонус дается, если мономино разыгрывается на последнем ходу. Побеждает игрок, у которого осталось наименьшее количество блоков.

Игра Cathedral также основана на полимино .

В 1966 году компания Parker Brothers выпустила многопользовательскую настольную игру в пентамино под названием «Вселенная». Ее тема основана на удаленной сцене из фильма 1968 года « 2001: Космическая одиссея» , в которой астронавт играет в игру в пентамино для двух игроков против компьютера HAL 9000 ( сцена с другим космонавтом, играющим в шахматы сохранена ). На лицевой стороне коробки с настольной игрой изображены сцены из фильма, а также подпись, описывающая ее как «игра будущего». В игру входят четыре набора пентамино красного, желтого, синего и белого цветов. На доске есть две игровые области: базовая зона 10х10 для двух игроков и дополнительные 25 клеток (еще два ряда по 10 и один смещенный ряд по пять) с каждой стороны для более чем двух игроков.

У производителя игр Lonpos есть ряд игр, в которых используются одни и те же пентамино, но в разных игровых плоскостях. Их 101 Game имеет самолет 5 x 11. Изменяя форму плоскости, можно разгадать тысячи головоломок, хотя в печати доступна лишь относительно небольшая подборка этих головоломок.

Видеоигры

• Тетрис был вдохновлен головоломками пентамино, хотя в нем используются тетромино из четырех блоков. Некоторые клоны и варианты тетриса, такие как игра 5, включенная в Plan 9 от Bell Labs , и Magical Tetris Challenge , действительно используют пентамино.
• Daedalian Opus на протяжении всей игры использует головоломки пентамино.

Литература

Пентамино были показаны в известном сюжете романа Артура Кларка 1975 года « Имперская земля» . Кларк также написал эссе, в котором описал игру и то, как он подсел на нее.

Они также были показаны в книге Blue Balliett « В погоне за Вермеером» , которая была опубликована в 2003 году и иллюстрирована Бреттом Хелквистом , а также в ее продолжениях, «Райт 3» и «Игра Колдера» .

В The New York Times кроссворде от 27 июня 2012 года подсказкой к слову из 11 букв и диаметром 37 была «Полный набор из 12 фигур, образованных черными квадратами этой головоломки».

См. также

Предыдущие и следующие заказы

• Тетромино
• Гексомино

Другие

• Плитка-головоломка
• «Собор» Настольная игра
• Соломон В. Голомб

Ссылки

• В погоне за Вермеером , с информацией о книге «В погоне за Вермеером» и доской для пентамино, которую можно перетаскивать.
• Причард, Д.Б. (1982). «Игра Голомба». Мозговые игры . Пингвин Букс Лтд . стр. 83–85. ISBN  0-14-00-5682-3 .

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

• Конфигурации и решения пентомино. Исчерпывающий список решений многих классических задач, показывающий, как каждое решение связано с другими.