Пентамино (или 5-омино ) , происходящее от греческого слова « 5 » и « домино », представляет собой полимино 5-го порядка; то есть многоугольник на плоскости , состоящий из 5 квадратов одинакового размера, соединенных ребром к краю. Если вращения и отражения не считаются отдельными формами, существует 12 различных свободных пентамино. Когда отражения считаются отдельными, получается 18 односторонних пентамино. Если вращения также считаются отдельными, существует 63 фиксированных пентамино.
Головоломки и игры с мозаикой пентамино популярны в развлекательной математике . [1] Обычно видеоигры , такие как имитации Тетриса и Rampart, считают зеркальные отражения отдельными и поэтому используют полный набор из 18 односторонних пентамино. (В самом тетрисе используются фигуры из 4 квадратов.)
Каждое из двенадцати пентамино удовлетворяет критерию Конвея ; следовательно, каждое пентамино способно замостить плоскость . [2] Каждое киральное пентамино может замостить плоскость, не отражаясь. [3]
Самая ранняя головоломка, содержащая полный набор пентамино, появилась в книге Генри Дюдени « Кентерберийские головоломки» , опубликованной в 1907 году . Дальнейшие проблемы с мозаикой были исследованы в PFCS и его преемнике Fairy Chess Review . [5] [6] : 127
Пентомино были формально определены американским профессором Соломоном В. Голомбом, начиная с 1953 года, а затем в его книге 1965 года «Полимино: головоломки, закономерности, проблемы и упаковки» . [1] [7] Они были представлены широкой публике Мартином Гарднером в его колонке «Математические игры» в октябре 1965 года в журнале Scientific American . Голомб придумал термин «пентамино» от древнегреческого πέντε / pénte , «пять», и -omino от домино , причудливо интерпретируя букву «d-» в слове «домино», как если бы это была форма греческого префикса «ди- " (два). Голомб назвал 12 свободных пентамино в честь букв латинского алфавита , на которые они похожи, используя мнемонику FILiPiNo вместе с концом алфавита (TUVWXYZ). [8] : 23
Джон Хортон Конвей предложил альтернативную схему обозначения пентамино, используя O вместо I, Q вместо L, R вместо F и S вместо N. Сходство с буквами более натянутое, особенно для пентамино О, но это Преимущество схемы заключается в использовании 12 последовательных букв алфавита. Он традиционно используется при обсуждении « Игры жизни» Конвея , где, например, говорится о R-пентамино вместо F-пентамино.
Пентамино 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:
Для 2D-фигур вообще есть еще две категории:
Стандартная головоломка пентамино состоит в том, чтобы замостить прямоугольную коробку пентамино, то есть покрыть ее без перекрытия и без пробелов. Площадь каждого из 12 пентамино равна 5 квадратам, поэтому площадь коробки должна составлять 60 единиц. Возможные размеры: 6×10, 5×12, 4×15 и 3×20.
Случай 6×10 был впервые решен в 1960 году Колином Брайаном Хазелгроувом и Дженифер Хазелгроув . [9] Существует ровно 2339 решений, исключая тривиальные варианты, полученные вращением и отражением всего прямоугольника, но включая вращение и отражение подмножества пентамино (что иногда дает простое дополнительное решение). В ящике 5×12 содержится 1010 решений, в ящике 4×15 — 368 решений, а в ящике 3×20 — всего 2 решения (одно показано на рисунке, а другое можно получить из решения, показанного вращением). в целом блок, состоящий из пентамино L, N, F, T, W, Y и Z).
Несколько более простая (более симметричная) головоломка — прямоугольник 8×8 с отверстием 2×2 в центре — была решена Даной Скотт еще в 1958 году. [10] Всего существует 65 решений. Алгоритм Скотта был одним из первых применений компьютерной программы поиска с возвратом . Вариации этой головоломки позволяют разместить четыре отверстия в любом положении. Одна из внешних ссылок использует это правило.
Эффективные алгоритмы для решения таких проблем были описаны, например, Дональдом Кнутом . [11] Эти головоломки пентамино, работающие на современном оборудовании , теперь можно решить за считанные секунды.
Большинство таких шаблонов разрешимы, за исключением размещения каждой пары отверстий рядом с двумя углами доски таким образом, чтобы оба угла могли быть вставлены только P-пентамино, или принудительного размещения Т-пентамино или U-пентамино в угол так, чтобы образовалось еще одно отверстие.
Набор пентамино — единственный свободный набор полимино, который можно упаковать в прямоугольник, за исключением тривиальных наборов мономино и домино , каждый из которых состоит только из одного прямоугольника.
Пентакуб – это многокуб из пяти кубов. Из 29 пентакубов ровно двенадцать пентакубов являются плоскими (1-слойными) и соответствуют двенадцати пентамино, выдавленным на глубину одного квадрата.
Головоломка с пентакубами или 3D- головоломка с пентамино представляет собой заполнение трехмерной коробки 12 плоскими пентакубами, то есть покрытие ее без перекрытия и без пробелов. Поскольку объем каждого пентакуба равен 5 единичным кубам, объем коробки должен составлять 60 единиц. Возможные размеры: 2×3×10 (12 решений), 2×5×6 (264 решения) и 3×4×5 (3940 решений). [12]
В качестве альтернативы можно также рассмотреть комбинации из пяти кубов, которые сами по себе являются трехмерными, то есть те, которые включают в себя больше, чем просто 12 «плоских» однослойных толстых комбинаций кубов. Однако в дополнение к 12 «плоским» пентакубам, образованным путем выдавливания пентамино, существует 6 наборов хиральных пар и 5 дополнительных частей, образующих в общей сложности 29 потенциальных частей пентакуба, что в общей сложности дает 145 кубов (= 29 × 5). ; поскольку 145 можно упаковать только в коробку размером 29×5×1, его нельзя сформировать путем включения неплоских пентамино.
Существуют настольные игры на ловкость, полностью основанные на пентамино. Такие игры часто называют просто «Пентомино».
Одна из игр проводится на сетке 8х8 двумя или тремя игроками. Игроки по очереди размещают пентамино на доске так, чтобы они не перекрывались с существующими плитками и чтобы ни одна плитка не использовалась более одного раза. Цель — стать последним игроком, положившим плитку на доску. Эта версия пентамино называется «Игра Голомба». [13]
Версия для двух игроков была слабо решена в 1996 году Хилари Орман. Исследование около 22 миллиардов позиций на доске доказало, что это победа первого игрока. [14]
Пентамино и подобные формы также являются основой ряда других игр, узоров и головоломок. Например, во французской настольной игре «Блокус» используются 4 цветных набора полимино , каждый из которых состоит из пентамино (12), тетромино (5), триомино (2), домино (1) и мономино (1). Как и в игре «Пентомино» , цель состоит в том, чтобы использовать все ваши плитки, и бонус дается, если мономино разыгрывается на последнем ходу. Побеждает игрок, у которого осталось наименьшее количество блоков.
Игра Cathedral также основана на полимино . [15]
Компания Parker Brothers выпустила многопользовательскую настольную игру с пентамино под названием «Вселенная» в 1966 году. Ее тема основана на удаленной сцене из фильма 1968 года «2001: Космическая одиссея» , в которой астронавт играет в пентамино для двух игроков против компьютера HAL 9000 ( сохранена сцена с другим космонавтом, играющим в шахматы ). На лицевой стороне коробки с настольной игрой изображены сцены из фильма, а также подпись, описывающая ее как «игра будущего». В игру входят четыре набора пентамино красного, желтого, синего и белого цветов. На доске есть две игровые области: базовая зона 10x10 для двух игроков и дополнительные 25 клеток (еще два ряда по 10 и один смещенный ряд по пять) с каждой стороны для более чем двух игроков.
У производителя игр Lonpos есть ряд игр, в которых используются одни и те же пентамино, но в разных игровых плоскостях. Их 101 Game имеет самолет 5 x 11. Изменяя форму плоскости, можно разгадать тысячи головоломок, хотя в печати доступна лишь относительно небольшая подборка этих головоломок.
Пентомино были показаны в известном сюжете романа Артура Кларка « Имперская земля» 1975 года . Кларк также написал эссе, в котором описал игру и то, как он подсел на нее. [16]
Они также были показаны в книге Blue Balliett « В погоне за Вермеером» , которая была опубликована в 2003 году и иллюстрирована Бреттом Хелквистом , а также в ее продолжениях, «Райт 3» и «Игра Колдера» . [17]
В кроссворде The New York Times от 27 июня 2012 года подсказкой к слову из 11 букв и диаметром 37 была «Полный набор из 12 фигур, образованных черными квадратами этой головоломки». [18]
