Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
12 пентамино могут образовывать 18 различных форм, причем 6 из них (хиральные пентамино) являются зеркальными.

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

Pentomino облицовочная головоломки и игры популярны в рекреационных математике . [1] Обычно в видеоиграх, таких как имитации тетриса и Rampart, зеркальные отражения рассматриваются как отдельные, и поэтому используется полный набор из 18 односторонних пентамино.

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

История [ править ]

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

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

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

Симметрия [ править ]

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

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

Например, восемь возможных ориентаций пентамино L, F, N, P и Y следующие:

    

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

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

Построение прямоугольных размеров [ править ]

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

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

Несколько более простая (более симметричная) головоломка, прямоугольник 8 × 8 с отверстием 2 × 2 в центре, была решена Даной Скотт еще в 1958 году. [6] Есть 65 решений. Алгоритм Скотта был одним из первых приложений компьютерной программы с возвратом . Варианты этой головоломки позволяют разместить четыре отверстия в любом положении. Одна из внешних ссылок использует это правило. Большинство таких шаблонов разрешимы, за исключением размещения каждой пары отверстий рядом с двумя углами доски таким образом, чтобы оба угла могли быть установлены только с помощью P-пентамино, или принудительного использования T-пентомино или U-пентамино в угол так, чтобы образовалось еще одно отверстие.

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

Решение мозаики прямоугольников полимино с n ячейками существует только для n = 0, 1, 2 и 5; первые три тривиальны.

Заполнение ящиков [ править ]

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

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

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

Настольная игра [ править ]

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

В одну из игр играют на сетке 8 × 8 два или три игрока. Игроки по очереди кладут пентамино на доску так, чтобы они не перекрывали существующие плитки и ни одна плитка не использовалась более одного раза. Цель состоит в том, чтобы быть последним игроком, разместившим плитку на доске. Эта версия пентамино называется «Игра Голомба». [9]

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

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

Игра Собор также основана на полимино . [11]

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

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

Литература [ править ]

Первая задача пентамино , написанная Генри Дудени , была опубликована в 1907 году в журнале Canterbury Puzzles. [12]

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

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

Видеоигры [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

  1. ^ a b Эрик Харшбаргер - Пентамино
  2. Перейти ↑ Rhoads, Glenn C. (2003). Плоские мозаики и поиск апериодического прототила . Кандидатская диссертация, Университет Рутгерса.
  3. ^ Гарднер, Мартин (август 1975). «Еще о мозаике плоскости: возможности полимино, полиалмазов и полигексов». Scientific American . 233 (2): 112–115.
  4. ^ people.rit.edu - Введение - полимино и пентамино
  5. ^ CB Haselgrove; Дженифер Хазелгроув (октябрь 1960 г.). «Компьютерная программа для пентамино» (PDF) . Эврика . 23 : 16–18.
  6. ^ Дана С. Скотт (1958). «Программирование комбинаторной головоломки». Технический отчет № 1, кафедра электротехники, Принстонский университет.
  7. ^ Дональд Э. Кнут. «Танцующие ссылки» (Postscript, 1,6 мегабайта). Включает резюме статей Скотта и Флетчера.
  8. ^ Барекет, Гилл; Тал, Шахар (2010). «Решение общих головоломок». Ли, Дер-Цай; Чен, Дэнни З .; Инь, Ши (ред.). Границы алгоритмики . Берлин Гейдельберг: Springer Science + Business Media . стр.  124 -135. DOI : 10.1007 / 978-3-642-14553-7_14 .
  9. Перейти ↑ Pritchard (1982) , p. 83.
  10. ^ Хилари К. Орман. Пентамино: Победа первого игрока (Pdf).
  11. ^ FAQ
  12. ^ Пентамино
  13. ^ Не могли бы вы решить пентамино? Артур Кларк, журнал Sunday Telegraph , 14 сентября 1975 г .; перепечатано в книге Кларка « Восхождение на орбиту: научная автобиография» , Нью-Йорк: John Wiley & Sons, 1984. ISBN 047187910X 
  14. ^ Погоня Vermeer , по Блу Баллиетт, Scholasticмягкой обложке, ISBN 0439372976 

Ссылки [ править ]

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

Внешние ссылки [ править ]

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