Что такое полимино и пентамино
Полимино — это плоские геометрические фигуры, составленные из одинаковых квадратов, соединённых сторонами. Термин придумал американский математик Соломон Вольф Голомб в 1953 году. В зависимости от числа квадратов в фигуре выделяют мономино (1), домино (2), тримино (3), тетрамино (4), пентамино (5), гексамино (6) и так далее. Наибольшую известность получило именно пентамино — набор фигур из пяти квадратов, ставший одной из самых популярных геометрических головоломок XX века.
12 фигур пентамино
Существует ровно 12 различных фигур пентамино (с точностью до поворотов и отражений). Каждая фигура традиционно обозначается латинской буквой, напоминающей её форму: F, I, L, N, P, T, U, V, W, X, Y и Z. Общая площадь всех 12 фигур составляет 12 × 5 = 60 квадратных клеток. Если учитывать зеркальные отражения как отдельные фигуры, то набор увеличивается до 18 односторонних пентамино (фигуры F, L, N, P, Y и Z имеют зеркальные пары, а I, T, U, V, W и X симметричны).
Классические задачи
Главная задача пентамино — уложить все 12 фигур без пропусков и наложений в прямоугольник. Поскольку суммарная площадь равна 60 клеткам, возможны прямоугольники 6×10, 5×12, 4×15 и 3×20. Количество решений для каждого формата: 6×10 — 2 339 решений, 5×12 — 1 010, 4×15 — 368, 3×20 — всего 2 решения. Эти числа были определены с помощью компьютерного перебора. Другие классические задачи включают составление фигуры, подобной одной из 12 пентамино, но увеличенной в три раза (из девяти оставшихся фигур), и покрытие шахматной доски 8×8 с четырьмя пустыми клетками.
История
Хотя формальное определение пентамино принадлежит Голомбу (1953), головоломки с подобными фигурами существовали и раньше. Широкую известность пентамино получило после публикации Мартина Гарднера в колонке «Математические игры» журнала Scientific American в октябре 1965 года. В 1960–1980-е годы головоломка была чрезвычайно популярна в СССР, где выпускались пластиковые и деревянные наборы, а задачи с пентамино включались в математические олимпиады. Компьютерная игра Tetris (1984, Алексей Пажитнов) использует фигуры тетрамино — ближайшего родственника пентамино.
Таблица семейства полимино
| Название | Число клеток | Количество фигур | Площадь набора |
|---|---|---|---|
| Мономино | 1 | 1 | 1 |
| Домино | 2 | 1 | 2 |
| Тримино | 3 | 2 | 6 |
| Тетрамино | 4 | 5 | 20 |
| Пентамино | 5 | 12 | 60 |
| Гексамино | 6 | 35 | 210 |
Интересный факт
Задачу укладки прямоугольника 6×10 из 12 пентамино полностью решил компьютер ещё в 1960-х годах — это был один из ранних примеров применения ЭВМ для комбинаторных задач. Общее число позиций для проверки при укладке 12 фигур в прямоугольник исчисляется миллионами вариантов, что делает ручное решение крайне трудоёмким.
