Пентаміно (від грец. Πέντα п'ять. І доміно) - Полімін з п'яти однакових квадратів, тобто плоскі фігури, кожна з яких складається з п'яти однакових квадратів, з'єднаних між собою сторонами ( «ходом тури»). Цим же словом іноді називають головоломку, в якій такі фігури потрібно укладати в прямокутник або інші форми.
Види і кількість фігур
Всього існують 12 різних фігур (елементів) пентаміно, що позначаються латинськими літерами, форму яких вони нагадують (див. Малюнок). Вважається, що дзеркальна симетрія і обертальна симетрія не створюють нових фігур. Але якщо вважати і дзеркально відбиті фігури, то їх число збільшиться до 18. Така відмінність має значення, наприклад, у комп'ютерній грі, варіації «Тетріс» - «Пентіксе».
- L, N, P, F і Y можуть бути орієнтовані 8 способами кожна: 4 поворотами і ще 4 дзеркальними відображеннями.
- Z може бути орієнтована 4 способами: 2 - поворотами, 2 - дзеркальними відображеннями.
- T, V, U і W можуть бути орієнтовані поворотами 4 способами кожна.
- I може бути орієнтована поворотами 2 способами.
- X може бути орієнтована єдиним способом.
Звідси число фіксованих пентаміно дорівнює 5 × 8 + (1 + 4) × 4 + 2 + 1 = 63.
Наприклад, ось вісім можливих способів орієнтації пентаміно L, F, P, N і Y:
Складання фігур з пентаміно
Укладання прямокутників
Прямокутники, складені з пентаміно
Найпоширеніша завдання про пентаміно - скласти з усіх фігурок, без перекриттів і зазорів, прямокутник. Оскільки кожна з 12 фігур включає в себе 5 квадратів, то прямокутник повинен бути площею 60 одиничних квадратів. Можливі прямокутники 6 × 10, 5 × 12, 4 × 15 і 3 × 20. Кожну з цих головоломок можна вирішити вручну, але більш складним завданням є підрахунок загального числа можливих рішень в кожному випадку. (Очевидно, прямокутники 2 × 30 і 1 × 60 скласти з пентаміно неможливо, оскільки багато фігур в них просто не поміщаються по ширині.)
Для випадку 6 × 10 це завдання вперше вирішив в 1965 році Джон Флетчер [1]. Існує рівно 2339 різних укладок пентаміно в прямокутник 6 × 10, не рахуючи поворотів і відображень цілого прямокутника, але вважаючи повороти і відображення його частин (іноді всередині прямокутника утворюється симетрична комбінація фігур, повертаючи яку можна отримати додаткові рішення; для прямокутника 3 × 20, наведеного на малюнку, друге рішення можна отримати поворотом блоку з 7 фігур, або, інакше кажучи, якщо поміняти місцями чотири фігури, крайні зліва, і одну крайню праворуч).
Для прямокутника 5 × 12 існує 1010 рішень, 4 × 15 - 368 рішень, 3 × 20 - всього 2 рішення (що відрізняються вищеописаним поворотом). Зокрема, існує 16 способів скласти два прямокутника 5 × 6, з яких можна скласти як прямокутник 6 × 10, так і 5 × 12.
Укладання прямокутників з односторонніх пентаміно
Якщо доповнити набір пентаміно дзеркальними копіями фігур, які не збігаються зі своїми відображеннями (F, L, P, N, Y і Z), то з повного набору в 18 односторонніх пентаміно можна скласти прямокутники площею 90 одиничних квадратів (при цьому фігури не дозволяється перевертати) . Завдання щодо складання прямокутника 3 × 30 має 46 рішень, 5 × 18 - понад 600 тис. Рішень, 6 × 15 - більше 2 млн. Рішень і 9 × 10 - більше 10 млн. Рішень [2]
Укладання фігур з отворами
В якійсь мірі більш просту (більш симетричну) завдання, для квадрата 8 × 8 з отвором в центрі 2 × 2, вирішив ще в 1958 році Дана Скотт [3] (аспірант-математик Прінстона). Для цього випадку існує 65 рішень. Алгоритм Скотта був одним з перших застосувань комп'ютерної програми пошуку з поверненням.
Квадрати з отворами, складені з пентаміно
Квадрати з отворами, які не можна скласти з пентаміно
Інший варіант цієї головоломки - викладання квадрата 8 × 8 з 4 отворами в довільно заданих місцях. Більшість таких завдань мають рішення. Винятком є випадки з розміщенням двох пар отворів поблизу двох кутів дошки так, щоб в кожен кут можна було помістити тільки P-пентаміно, або всіх чотирьох отворів поблизу одного кута так, що при будь-якому можливому заповненні кутовий клітини (за допомогою U- або T- пентаміно) від дошки відсікається ще одна клітина (див. малюнок).
Для вирішення цих завдань ефективні алгоритми описав, наприклад, Дональд Кнут [4]. На сучасному комп'ютері подібні головоломки вирішуються за лічені секунди.
Питання про потроєння фігур пентаміно
Це завдання було запропоновано професором Каліфорнійського університету Р.М.Робінсоном. Вибравши одну з 12 фігур пентаміно, необхідно побудувати з будь-яких 9 з 11 залишилися пентаміно фігуру, подібну обраної, але в 3 рази більшої довжини і ширини. Рішення існує для будь-якого з 12 пентаміно, причому не єдине (від 15 рішень для Х до 497 для Р). [2] Існує варіант цього завдання, в якому для побудови потроєною фігури дозволяється використовувати також і саму вихідну фігуру. У цьому випадку число рішень від 20 для Х до 9144 для Р-пентаміно. [5]
Представлене на малюнку рішення [6]. знайдене А. Ван де Ветерінг, володіє цікавою властивістю: кожне пентаміно використовується для потроєння дев'яти з інших, по одному разу в кожній. Таким чином, з 9 комплектів вихідних фігур пентаміно можна одночасно скласти всі 12 потроєних пентаміно.
Настільна гра
Пентаміно може використовуватися також як настільна гра для двох гравців. [7] Для гри необхідна шахівниця 8 × 8 і набір фігур пентаміно, клітини яких мають однаковий розмір з клітинами дошки. На початку гри дошка порожня. Гравці по черзі виставляють на дошку по одній фігурі, закриваючи 5 вільних клітин дошки. Всі виставлені фігури залишаються на місці до кінця партії (не знімаються з дошки і не пересуваються). Тим, хто програв вважається гравець, який першим не зможе зробити ходу (або через те, що жодна з решти фігур не вміщується на вільних ділянках дошки, або тому, що всі 12 фігур вже виставлені на дошку).
Аналіз гри досить складний (так, на початку є навіть більше можливих перших ходів, ніж в шахах). Голомб запропонував наступну стратегію: прагнути розбити вільне місце на дошці на два рівновеликих ділянки (і перешкодити суперникові зробити це). Після цього на кожен хід суперника на одній з ділянок слід відповідати ходом на іншому.
Приклад партії в пентаміно показаний на малюнку. Нумерація ходів наскрізна (непарні номери ходів належать першому гравцеві, парні - другого). Спочатку гравці роблять ходи в центрі дошки (ходи 1-3), не дозволяючи одна одній розбити дошку на рівновеликі ділянки. Але потім другий гравець робить невдалий хід (4), що дозволяє супернику розбити вільне місце на дві ділянки по 16 клітин (хід 5). (В цьому прикладі вільні ділянки не тільки рівні по площі, але і збігаються за формою - симетричні щодо діагоналі дошки, але для стратегії це, зрозуміло, не обов'язково.) Далі на хід другого гравця (6) на одному з цих ділянок перший гравець відповідає ходом на іншому (7) і виграє. Хоча на дошці ще є три вільних ділянки в п'ять і більше клітин, але всі підходящі фігури (I, P, U) вже використані.
Варіанти настільної гри
Пентаміно із заздалегідь вибраними фігурами
У цьому варіанті гри гравці спочатку по черзі вибирають по одній фігурі, поки все фігури не будуть розподілені між ними. Далі гра проходить за правилами звичайного пентаміно, з тією різницею, що кожному з гравців дозволяється ходити тільки тими фігурами, які він вибрав. Який узяв останню фігуру робить перший хід.
Стратегія цього варіанту гри, запропонована Голомбом, істотно відрізняється від стратегії звичайного пентаміно. Замість того, щоб розбити дошку на рівновеликі ділянки, гравець прагне створити на дошці ділянки, які можна заповнити лише його фігурами, але не фігурами суперника. (Голомб називає такі ділянки «притулками».)
Приклад партії в пентаміно із заздалегідь вибраними фігурами показаний на малюнку. Фігури, обрані першим і другим гравцями, перераховані зліва і праворуч від дошки відповідно. Закреслено буква позначає, що фігура використана для ходу. Спочатку гравці позбавляються від самих «незручних» фігур X і W (ходи 1 та 2). Потім перший гравець створює «притулок» для фігури Y (хід 3), другий - для фігур U і P (ходи 4 і 6). В кінці партії (ходи 8-10) відбувається заповнення цих «притулків» і партія закінчується перемогою другого гравця - у першого залишається Т-образне пентаміно, для якого на частини дошки немає відповідного місця.
Інші варіанти
- «Картярське пентаміно» - варіант гри з привнесенням випадкових подій. Фігури пентаміно (або їх буквені позначення) малюють на картках, які тасують і роздають гравцям. Гравці вибирають фігури відповідно до розданими їм картками. Далі гра йде за правилами пентаміно із заздалегідь вибраними фігурами.
- Пентаміно для чотирьох гравців. Чотири гравці, що сидять по чотирьох сторонах дошки, грають двоє на двоє (гравці, які сидять один навпроти одного, утворюють команду). Програла вважається команда, гравець якої першим не зможе зробити ходу. У цю гру можна грати за допомогою одного з трьох вищеописаних варіантів - звичайному, з заздалегідь вибраними фігурами або «картковому».
- «Хтось кого?» У грі бере участь від двох до чотирьох гравців, але кожен з них грає тільки за себе. Переможцем вважається який зробив останній хід, йому зараховується 10 очок. Гравець, який повинен ходити після переможця (тобто першим не зможе зробити ходу) отримує 0 очок, а всі інші гравці - по 5 очок. Може бути зіграно кілька партій, набрані в них очки сумуються. Гра також може проводитися за допомогою одного з трьох вищеописаних варіантів правил.
Комп'ютерні ігри
Примітки
ПОЛІФОРМ
Дивитися що таке "пентаміна" в інших словниках:
Пентаміно (гра) - пентаміно (від ін. Грец. Πέντα п'ять, і доміно) Полімін з п'яти однакових квадратів, тобто плоскі фігури, кожна з яких складається з п'яти однакових квадратів, з'єднаних між собою сторонами ( «ходом тури»). Цим же словом іноді називають ... Вікіпедія
Полімін - Полімін, або поліоміно (англ. Polyomino) плоскі геометричні фігури, утворені шляхом з'єднання декількох рівних квадратів по їх сторонам. Це ПОЛІФОРМ, сегменти яких є квадратами. Їх можна розглядати як кінцеві ... Вікіпедія
Гексамін - гексамін Полімін 6 го порядку, тобто плоска фігура, що складається з шести рівних квадратів, з'єднаних сторонами. З фігурами гексамін, як з усіма Полімін, пов'язано багато завдань цікавої математики ... Вікіпедія
Тетраміно - Односторонні фігури тетраміно: I, J, L, O, S, T, Z тетраміно геометричні фігури, що складаються з чотирьох квадратів, соед ... Вікіпедія
- Стомахіон. Гра Піфагора. Пентаміно. ЗГГ. Драко. Звертаючись в книзі гри мають тисячолітню історію. Дано силуети фігур, які треба зібрати з окремих деталей. Кожна з наведених ігор має свій комплект деталей, з яких можна ... Детальніше Купити за 241 руб
- Стомахіон. Гра Піфагора. Пентаміно. М. Драко. Зібрані в книзі гри мають тисячолітню історію. Дано силуети фігур, які треба зібрати з окремих деталей. Кожна з наведених ігор має свій комплект деталей, з яких можна ... Детальніше Купити за 219 руб
- Стомахіон. Гра Піфагора. Пентаміно: Ігри-головоломки. Драко Михайло. Зібрані в цій книзі гри мають тисячолітню історію - схильність до геометричних загадок властива людям різних епох і національностей. Однак мало хто ізетіх головоломок збереглися ... Детальніше Купити за 152 руб